网站建设实训目的,心理咨询网站后台,厦门人才网招聘官网,在湖南建设人力资源网站查找剑指 Offer 03. 数组中重复的数字剑指 Offer 53 - I. 在排序数组中查找数字 I二分法题目链接剑指 Offer 03. 数组中重复的数字 题#xff1a;在一个长度为 n 的数组 nums 里的所有数字都在 0#xff5e;n-1 的范围内。数组中某些数字是重复的#xff0c;但不知道有几个数…
查找剑指 Offer 03. 数组中重复的数字剑指 Offer 53 - I. 在排序数组中查找数字 I二分法题目链接剑指 Offer 03. 数组中重复的数字 题在一个长度为 n 的数组 nums 里的所有数字都在 0n-1 的范围内。数组中某些数字是重复的但不知道有几个数字重复了也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 思路是先给数组排序遍历过程中与后一个值相等说明有重复直接输出即刻但是使用len()一直报错不知道原因
#报错!!Why
class Solution:def findRepeatNumber(self, nums: List[int]) - int:numsnums.sort()for i in range(0,len(nums)-1):if nums[i]nums[i1]: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获取每个元素索引和值cont0for index,v in enumerate(nums):if(vtarget):contcont1return 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
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
