题目描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。
思路:
这个题目的特点:数组中的数字都在0到n-1之间。
如果数组中没有重复的数字,那么拍好序之后,数字i一定出现在第i 的位置上。
如果有重复的数字,那么某个位置可能存在多个数字,或者某个位置上没有数字。
从头依次扫描数组
扫描到下标为i时候,判断i与当前的数a[i]是否相等
相等,继续扫描下一个
不相等: 交换i与a[i]位置的元素。不断循环。
当位置i的元素与a[i]的元素相等时,找到了重复的元素。
1 public class Solution { 2 // Parameters: 3 // numbers: an array of integers 4 // length: the length of array numbers 5 // duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation; 6 // Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++ 7 // 这里要特别注意~返回任意重复的一个,赋值duplication[0] 8 // Return value: true if the input is valid, and there are some duplications in the array number 9 // otherwise false 10 public boolean duplicate(int a[],int length,int [] duplication) { 11 if(length<=0||a.length<=0) return false; 12 for(int i = 0;i<length;i++){ 13 while(i!=a[i]){ 14 if(a[i]==a[a[i]]){ 15 duplication[0] = a[i]; 16 return true; 17 } 18 swap(a,i,a[i]); 19 } 20 } 21 return false; 22 } 23 private void swap(int[] a ,int i,int j){ 24 int temp = a[i]; 25 a[i] = a[j]; 26 a[j] = temp; 27 } 28 }