面试题03. 数据中的重复数字

题目描述

找出 [2, 3, 1, 0, 2, 5, 3] 中的任意重复数字

做题链接： 面试题03. 数据中的重复数字

解题思路

方法一： 利用下标信息【Best Answer】

nums 里的所有数字都在 0～n-1 的范围内，这一条件表示 每个数字都只有一个坑位，一个坑位上不能有两个数字

时间复杂度 $O(n)$ 空间复杂度 $O(1)$

• 交换数组的时候，需要注意使用 python 便捷的交换方式会存在陷阱

  # 正确方法一：
  temp = nums[i]
  nums[i] = nums[nums[i]]
  nums[temp] = temp
  
  # 正确方法二：
  nums[nums[i]] , nums[i] = nums[i] , nums[nums[i]]
  
  # 错误方式：
  nums[i], nums[nums[i]] = nums[nums[i]], nums[i]

方法二：哈希表法

时间复杂度 O(n) 空间复杂度O(n)

• 可以通过 集合， 字典 两种方式实现

代码

方法一

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
       for i in range(len(nums)):
           while i != nums[i]:
               if nums[i] == nums[nums[i]]: return nums[i]
               # 原地交换
               temp = nums[i]
               nums[i] = nums[nums[i]]
               nums[temp] = temp
               

方法二

  # 基于集合
  class Solution:
      def findRepeatNumber(self, nums: List[int]) -> int:
         s = set()
         for i in nums:
             if i in s: return i
             else: s.add(i)
  # 基于字典
  class Solution:
      def findRepeatNumber(self, nums: List[int]) -> int:
         s = dict()
         for i in nums:
             if i in s: return i
             else: s[i] = True