[JZ 数组中重复的数字]

方法一：最简单的一个想法是 先把数组进行排序，再在数组中找到重复的数字
排序，时间O(nlogn)，空间O(logn)，修改了原数据

import java.util.*;
class Solution {
    public int findRepeatNumber(int[] nums) {
        Arrays.sort(nums);
        int ans = 0;
        for(int i=1;i<nums.length;i++){
            if (nums[i] == nums[i-1]){
                ans = nums[i];
                return ans;
            }

        }
        return -1;
    }
}

方法二：还可以利用哈希表来解决该问题，没扫描到一个数字，若哈希表里已存在，就找到，否则加入 哈希表 hash表，时间O(n)，空间O(n)，不修改原数据

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

方法三：利用辅助数组，与方法2类似，时间O(n)，空间O(n)，不修改原数据

class Solution {
    public int findRepeatNumber(int[] nums) {
        int []nums2 = new int[nums.length];
        for (int i=0;i<nums.length;i++){
            nums2[nums[i]]++;
            if (nums2[nums[i]]>1)
                return nums[i];
        }
        return -1;
    }
}

方法四：鸽巢原理（一个萝卜一个坑）

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