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

数组长度为n，但数的范围在0到n-1。所以必定有重复。但直接遍历真的太憨憨了:sweat_smile:(是我没错了)。

• 使用哈希表的set()【集合】方法

set对象的每一个元素要求可进行哈希运算，set 会对内部元素进行去重，每个元素在同一个set 中只会出现一次;

字典可以将一个可哈希值映射到一个任意对象，可以通过映射关系快速查找对应数据；所以在dict中的每一项由一个key-value对组成(也称pairs) ，其中key 会作为字典快速查找的的一个关键数据，所以要求一个字典中键必须是唯一，并可哈希，若在赋值过程中出现相同的key值，后者将会覆盖之前的内容。

归根结底数据结构掌握不全。

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        s = set()
        for i in range(len(nums)):
            if nums[i] in s:
                return nums[i]
            s.add(nums[i]) 
        return -1

				

					
				
				

					
				
				

					
				
				

					
				
			

• 原地交换

结合题目，数组长度为n，但数的范围在0到n-1。因此，将索引与数值一一对应就可以找到重复的。

class Solution:
    def findRepeatNumber(self, nums) -> int:
        i=0
        while i < len(nums):
            if nums[i] == i: # 两个判断语句的顺序不能换；如果没有第一个判断第二个就会产生错误
                i=i+1
                continue
            if nums[nums[i]] == nums[i]:  # 找到重复就推出
                return nums[i]
 
            # 索引与值不对应就一直调换顺序，直到相同在去下一个位置；
            tmp = nums[i]
            nums[i] = nums[tmp]
            nums[tmp] = tmp
 
        return -1

				

					
				
				

					
				
				

					
				
				

					
				
			

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

刚开始自己的思路是使用二分查找法找到位置，再看目标数字出现的次数。但写的太麻烦了，还有好多错误。

• 改进二分法转换为寻找目标的左边界和右边界

左边界和右边界的寻找，也正好是我感到困难的地方。因为要顾及到是否超出列表的索引范围

    def search(nums, target: int) -> int:
        # 搜索右边界 right
        i, j = 0, len(nums) - 1
        while i <= j:
            m = (i + j) // 2
            if nums[m] <= target: i = m + 1  # 即使找到目标也将索引右移，最终索引的值刚好比目标值大
            else: j = m - 1
        right = i
        # 若数组中无 target ，则提前返回
        if j >= 0 and nums[j] != target: return 0
        # 搜索左边界 left
        i = 0
        while i <= j:
            m = (i + j) // 2
            if nums[m] < target: i = m + 1
            else: j = m - 1
        left = j
        return right - left - 1

				

					
				
				

					
				
				

					
				
				

					
				
			

引用

图解算法数据结构 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台