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

找出数组中重复的数字。

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

示例 1:


输入:

[2, 3, 1, 0, 2, 5, 3]

输出:2 或 3

限制:


2 <= n <= 100000

一解

利用临时变量tmp存储已遍历的数:


class Solution:

    def findRepeatNumber(self, nums: List[int]) -> int:

        tmp = []

        for num in nums:

            if num not in tmp:

                tmp.append(num)

            # 如果该数在 tmp 中,就确认有重复

            else:

                return num

  • 执行用时:5692ms,在所有 Python3 提交中击败了 7.74%的用户

  • 内存消耗:23.5MB,在所有 Python3 提交中击败了 27.25%的用户

一解的问题在于:

  • 使用临时数组消耗大量内存

  • if num not in tmp的 in 操作是 O(n) ,浪费时间

二解

使用原地 hash 思想,在位置 0 遇到元素 6 ,判断其值和位置 6 的值 10 是否相同。

不相同:将两者互换

image

相同:找到重复值,返回结果

image

一直重复此过程:


class Solution:

    def findRepeatNumber(self, nums: List[int]) -> int:

        n = len(nums)

        for i in range(n):

            # 只有 i != nums[i] 时,才说明要判断的两个元素在两个位置,即 nums[i] 和 nums[nums[i]] 不是同一个元素

            if i != nums[i]:

                if nums[i] == nums[nums[i]]:

                    return nums[i]

                tmp = nums[i]

                nums[i], nums[tmp] = nums[tmp], nums[i]

  • 执行用时:32ms,在所有 Python3提交中击败了99.79%的用户

  • 内存消耗:23.4MB,在所有 Python3提交中击败了52.83%的用户

class Solution():
def findRepeatNumber(self, nums):
lenth=len(nums)
while (lenth>0):
number=nums.pop()
nums=nums
if (number in nums)==True:
return number
break
lenth=len(nums)
return None

关闭