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

题目

找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入： [2, 3, 1, 0, 2, 5, 3] 输出：2 或 3
限制:
2 <= n <= 100000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

1. 超时解法

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        超时解法
        magic = -12323
        for i in range(len(nums)):
            num = nums[i]
            nums[i] = magic
            if num in nums:
                return num

这是最容易想到的解法，每次拿到一个数，都去原始的数组里面看看有没有其他的。同时为了不让自己和自己混淆，把这个数变成一个魔数，但是很遗憾超时了。

2. 排序算法

def findRepeatNumber(self, nums: List[int]) -> int:
        # 利用内置的sort函数
        nums.sort()
        for i in range(len(nums)-1):
            if nums[i] == nums[i+1]:
                return nums[i]

那么，不如首先对数组进行排序，这里的排序比如用快拍堆排就行了，为了方便我直接用了python内置的排序，虽然过了，但是为了找一个数对整个数组排序还是有点无用功。

3. hashset

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        # 哈希set解法
        tmp = set()
        for i in nums:
            if i in tmp:
                return i
            else:
                tmp.add(i)

因为hashset内的元素具有唯一性，而且hashset的复杂度较低，那我们从数组中取出数字加入到hashset中，如果发生了冲突就说明找到了。

4. 利用数组作为哈希表

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        # 注意到限定条件：在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。
        # 那就可以自己【手动】建立一个长度为n的“哈希表”，对应关系是n->n
        table = [-1]*len(nums)
        for i in nums:
            if table[i] == i:
                return i      # 发生了冲突
            else:
                table[i] = i    # 加入表

5. 不需要重新开辟空间的解

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:    
        # 开辟数组其实没有必要，我们可以在原有数组上进行操作
        # 思路对了，但是方法不对，这样的循环不能保证：比如i = 0 的位置是0
        # for i in range(len(nums)):
        #     if nums[i] != i:
        #         if nums[nums[i]] == nums[i]:
        #             return nums[i]
        #         else:
        #             nums[i],nums[nums[i]] = nums[nums[i]],nums[i]
        # 正确的
        i = 0
        while i < len(nums):
            if nums[i] != i :      # 如果下标和值不对应，那么这个数字就应该放在正确的位置
                if nums[i] != nums[nums[i]]:    # 放过去的数字上
                    # 交换
                    # nums[i],nums[nums[i]] = nums[nums[i]],nums[i]
                    t = nums[i]
                    nums[i],nums[t] = nums[t],nums[i]
                else:
                    return nums[i]        
            else:
                i += 1

我们可以知道，在n个元素的数组上，放下0~n-1的数字。如果没有重复的话，按照从小到大的顺序排列就是[0,1,2,3,4,5...,n-1]。
所以我们可以通过交换数组中元素的顺序，来还原为：数组上每个数字的位置就是该数组元素的值，也就是在第0个位置值为0，第一个元素值为1...

6. bonus 不修改数组的，不使用额外存储空间

TODO

最后编辑于：2020.06.18 00:03:51