03_数组中重复的数字

类型：数组

• 数组中重复的数字 💚

  https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/

  ❓ 长度为 n 的数组，元素范围在 0~n-1，找出其中任意一个重复的数字。

  💡 集合 + 一次遍历

  class Solution:
      def findRepeatNumber(self, nums: List[int]) -> int:
          se = set()
          for num in nums:
              if num in se:
                  return num
              else:
                  se.add(num)

  时间复杂度：O(N)，空间复杂度：O(N)

  💡 原地修改 - 代替哈希

  此方法会修改数组。

  当我们遍历到第 i 个元素的时候，它的值为 k = nums[i]，我们以 k 为下标，将 nums[k] -= n，由于数组元素值在 0~n-1 的范围内，那么 k 必然是合法的下标，且 nums[k] - n 必然小于 0. 因此当我们在某次访问到 nums[k] 小于 0 的时候，则说明它已经被修改过了，即值为 k 的元素已经出现过了。但是我们将 nums[k] -= n 破环了原数组，会不会造成信息损失呢，不必担心，我们在访问的时候再加上 n 即可。

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