LeetCode-面试题03-数组中重复的数字

题目

找出数组中重复的数字。

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

示例 1：

输入：

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

输出：2 或 3 

限制：

2 <= n <= 100000

解题思路

方法1、利用一个hash表，从头到尾扫描每个数字，不在表内的数字会成功添加，在表内的数字添加的时候会告诉已经存在，这个已经存在的数字就是要返回的数字了

方法2、这个思想很巧妙，也是剑指offer上的最优解，数组的数字都在0~n-1的范围内。如果这个数组中没有重复的数字，那么当数组排序之后数字i将会出现在下标为i的位置。从头到尾依次扫描这个数组中的数字，当扫描到下标为i的数字时，首先比较这个数字(用m表示)是不是等于i。如果是，则接着扫描下一个数字；如果不是，则再拿它和第m个数字进行比较。如果它和第m个数字相等，就找到了第一个重复的数字(该数字在下标为i和m的位置都出现了)；如果它和第m个数字不相等，就把第i个数字和第m个数字交换，把m放到属于它的位置。接下来再重复这个比较、交换的过程，直到发现一个重复的数字。

Java代码

class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> s = new HashSet<>();
        int result = -1;
        for (int i : nums) {
            if (!s.add(i)) {
                result = i;
                break;
            }
        }
        return result;
    }
}

Python代码

class Solution(object):
    def findRepeatNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for index, i in enumerate(nums):
            while (index != i):
                if (i == nums[index]):
                    return i
                temp = i
                i = nums[i]
                nums[i] = temp