剑指offer03-数组中重复的数字

题目链接：

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

题目描述：

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

其中，2 <= n <= 100000。

示例：

输入：[2,3,1,0,2,5,3]
输出：2或3

解法一：

常规思路，遍历数组，将元素添加到集合中，若出现重复元素则直接返回结果。

最坏情况下，重复的数字在最后才出现。

时间复杂度（最坏情况）：O(n)

空间复杂度（最坏情况）：O(n)

class Solution{
	public int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int num : nums){
            if(set.contains(num)){
                return num;
            }
            set.add(num);
        }
        return -1;
    }
}

解法二：

题目中已说明了数组中的数字范围在0到n-1之间，那么每个数字都可以放到其对应位置，例如数字0可以放到下标为0的位置，数字1可以放到下标为1的位置。

遍历数组，若当前数字不在它应在的位置，则与下标为当前数字的位置上的数字进行交换，重复，直到位置正确为止。

时间复杂度（均摊分析）：O(n)

空间复杂度：O(1)

class Solution{
	public int findRepeatNumber(int[] nums) {
        int n = nums.length;
        for(int i = 0; i < n; i++){
            while (nums[i] != i){
                if(nums[i] == nums[nums[i]]){
                    return nums[i];
                }
                swap(nums,i,nums[i]);
            }
        }
        return -1;
    }

    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

剑指offer03-数组中重复的数字

原文：https://www.cnblogs.com/iheaven/p/14646914.html