算法----找出重复数字

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

※可能附加时间/空间需求

相关标签：数组

eg.

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

解法一：

依次遍历数组，创建空集合，每次将遍历的元素放入集合，如果加入成功则继续，加入失败，表示存在重复元素，返回该元素。

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

解法二：

原地置换方法，读题可知，长度为你，元素都在0~n-1范围内，无重复元素情况下，正常升序排序，元素和下标一一对应。在有重复元素情况下，一次使用每一元素置换，直到置换到相应下标的为止，进行循环，如果循环中碰到置换后依旧相等的情况，就查找到了重复元素。

image-20210223114803461.png

class Solution {
    public 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;
    }
}