leecode-2 数组中重复的数

思路1

由题意可知：这个数组的值与数组的下标联系很深；
故可以遍历整个数组，定义一个数组，用count【i】记录i出现的次数，若count[i]>1则重复了，返回i。

public int findRepeatNumber(int[] nums) {
        
        int [] count =new int[nums.length];
    
        for(int temp : nums){
            count[temp]+=1;
            if(count[temp]>1)
                return temp;
        }
          
        return -1; 
    }

这个方式的时间复杂度为O(n) ,空间复杂度为O（n）

思路二

在原数组的基础上，进行数值交换，nums【i】存储 i 的值，一个萝卜一个坑，若nums【i】已经储存了一个
i 的值，则重复了，return nums[i] 。

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

这个算法的时间复杂度为O(n), 空间复杂度为O(1);