【Leetcode 剑指Offer】第 4 天 查找算法（简单）

题目链接

剑指 Offer 03. 数组中重复的数字

题：在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1
的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

思路是先给数组排序，遍历过程中与后一个值相等说明有重复，直接输出即刻，但是使用len()一直报错，不知道原因

#报错!!Why
class Solution:def findRepeatNumber(self, nums: List[int]) -> int:nums=nums.sort()for i in range(0,len(nums)-1):if nums[i]==nums[i+1]:return nums[i]

换了一个方法不用遍历：

class Solution:def findRepeatNumber(self, nums: List[int]) -> int:tmp = [0]*len(nums)for i in nums:tmp[i]+=1if tmp[i]>1:return i

剑指 Offer 53 - I. 在排序数组中查找数字 I

题：统计一个数字在排序数组中出现的次数。
最暴力的方法时间复杂度O(n):

class Solution:def search(self, nums: List[int], target: int) -> int:#enumerate获取每个元素索引和值cont=0for index,v in enumerate(nums):if(v==target):cont=cont+1return cont

二分法

进化一下，要使用二分法，使用二分法分别找到 左边界 left和 右边界 right，两者之差就是target的数量了。

复杂度分析：
时间复杂度 O(logN) ： 二分法为对数级别复杂度。
空间复杂度 O(1)： 几个变量使用常数大小的额外空间。

来源题解

class Solution:def search(self, nums: [int], target: int) -> int:# 搜索右边界 righti, j = 0, len(nums) - 1while i <= j:m = (i + j) // 2if nums[m] <= target: i = m + 1else: j = m - 1right = i# 若数组中无 target ，则提前返回if j >= 0 and nums[j] != target: return 0# 搜索左边界 lefti = 0while i <= j:m = (i + j) // 2if nums[m] < target: i = m + 1else: j = m - 1left = jreturn right - left - 1作者：Krahets
链接：https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/solutions/155893/mian-shi-ti-53-i-zai-pai-xu-shu-zu-zhong-cha-zha-5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。