题目描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

代码一

思想:
暴力

  1. public static boolean duplicate(int numbers[],int length,int [] duplication) {
  2.         if(numbers==null)return false;
  3.         int[] arr = new int[1];
  4.         boolean flag = false;
  5.         for(int i=0;i<numbers.length;i++) {
  6.             for(int j=i+1;j<numbers.length;j++) {
  7.                 if(numbers[i]==numbers[j]) {
  8.                     duplication[0] = numbers[i];
  9.                     return true;
  10.                 }
  11.             }
  12.         }        
  13.         return false;        
  14.     }

代码二

思想:哈希表

  1. public class Solution {
  2.     public boolean duplicate(int numbers[],int length,int [] duplication) {
  3.         Set<Integer> set = new HashSet<>();
  4.         for(int i =0 ;i<length;i++){
  5.             if(set.contains(numbers[i])){
  6.                 duplication[0] = numbers[i];
  7.                 return true;
  8.             }else{
  9.                 set.add(numbers[i]);
  10.             }
  11.         }
  12.         return false;
  13.     }
  14. }

代码三

解题思路
已知数组中的每一个数字值小于数组长度，如果数组中无任何重复的数字，则数组从小到大排序后理应满足第i个位置对应的元素值是i。利用此特性（数组{2, 3, 1, 0, 2, 5, 3}，指针’|’）：

  • |2 3 1 0 2 5 3
    指针’|’此时的位置是0，而数组中位置0的元素值是2，2 != 0，将数组中位置0与位置2的元素相互交换。
  • |1 3 2 0 2 5 3
    指针’|’的位置依然是0，而数组中位置0的元素值是1，1 != 0，将数组中位置0与位置1的元素相互交换。
  • |3 1 2 0 2 5 3
    指针’|’的位置依然是0，而数组中位置0的元素值是3，3 != 0，将数组中位置0与位置3的元素相互交换。
  • |0 1 2 3 2 5 3
    指针’|’的位置依然是0，但数组中位置0的元素值是0，0 == 0，将指针’|’右移一位。
  • 0 |1 2 3 2 5 3
    指针’|’此时的位置是1，但数组中位置1的元素值是1，1 == 1，将指针’|’右移一位。
  • 0 1 |2 3 2 5 3
    指针’|’此时的位置是2，但数组中位置2的元素值是2，2 == 2，将指针’|’右移一位。
  • 0 1 2 |3 2 5 3
    指针’|’此时的位置是3，但数组中位置3的元素值是3，3 == 3，将指针’|’右移一位。
  • 0 1 2 3 |2 5 3
    指针’|’此时的位置是4，而数组中位置4的元素值是2，2 != 4，且数组中位置4与位置2的元素值相等，那么输出此元素值。

思想:
利用题目的特性:数组中的value都小于数组长度,那么可以尝试让value和index(数组索引)归为(相对应比如arr[2]=2)
归位的方法:只要对应的arr[i]!=i,那么就找到索引等于arr[i]的,然后交换那么arr[i]就归位了.
找重复值方法:在归位的过程中,如果出现了当前值arr[current]能在前面归位的数中找到同它一样的就可以了

  1. public static boolean duplicate(int numbers[],int length,int [] duplication) {
  2.         if(numbers == null||length==0)return false;
  3.         for(int i=0;i<length;i++) {
  4.             while(numbers[i]!=i) {
  5.                 if(numbers[i]==numbers[numbers[i]]) {
  6.                     duplication[0] = numbers[i];
  7.                     return true;
  8.                 }else {
  9.                     int temp = numbers[i];
  10.                     numbers[i] = numbers[temp];
  11.                     numbers[temp] = temp;
  12.                 }                
  13.             }            
  14.         }
  15.         return false;        
  16.     }

代码四

思想:
就是利用题目的特性,数组中的元素值都小于数组的长度,那么我们想啊,既然要找数组中首先出现的重复值的元素,那么如果两个重复值当作为index索引的话必然两个都指向数组中同一个元素,所以我们只要找到这个这个元素就可以了.
这里我们怎么去找呢,我们在遍历数组的时候,将arr[index]作为索引找到对应的arr[arr[index]]将其标记以表示我们访问过了该元素,如果下次再访问到该元素那么也就是说我们找到了arr中两个重复值作为索引指向的同一个元素.
这里我们怎么去标记访问过的呢?我们通过给访问过的值加上数组长度存到数组中去,不断的去遍历数组下去这样下次如果有遇到arr[arr[index]]大于数组长度的(也就是说你对应的arr[arr[index]]已经操作过加数组长度的过程了),那么我们就找到了.

  1. public static int duplicate(int numbers[],int length) {
  2.       for ( int i= 0 ; i<length; i++) {
  4.             int index = numbers[i];
  6.             if (index >= length) {
  8.                 index -= length;
  10.             }   
  11.             if (numbers[index] >= length) {
  13.                 return index;
  15.             }   
  17.             numbers[index] = numbers[index] + length;
  19.         }   
  21.         return - 1 ;         
  22.     }