劍指offer面試題3，找出數(shù)組中的重復(fù)數(shù)字(java實現(xiàn))

給定一個長度為 n 的整數(shù)數(shù)組?num，數(shù)組中所有的數(shù)字都在 0～n的范圍內(nèi)。

數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個數(shù)字重復(fù)了，也不知道每個數(shù)字重復(fù)了幾次。

請找出數(shù)組中任意一個重復(fù)的數(shù)字。

解法：對于長度為n的數(shù)組，數(shù)字都在0~n之間。根據(jù)鴿籠原理，一定存在重復(fù)的數(shù)字。如果沒有重復(fù)度的數(shù)字，將數(shù)組排序之后所有的數(shù)字都和它的下標(biāo)是一致的。所以這里，我們可以將所有的數(shù)字放回到與它一致的下標(biāo)中，如果在下標(biāo)處已經(jīng)存在改數(shù)字，那么久找到了重復(fù)的數(shù)字。

public class RepeatNumber {

? ? public static void main(String[] args){

? ? ? ? RepeatNumber rn =new RepeatNumber();

? ? ? ????? int[] num =new int[]{2,3,1,0,2,5,3};

? ? ? ????? System.out.println(rn.repeatNumber(num));

? ? }

????public int repeatNumber(int[] num){

????????if(num.length==0)????return -1;

? ? ? ????? for(int i=0;i<num.length;){

? ? ? ? ? ? ? ? ? ?if(num[i] != i){

????????????????????????if(num[num[i]] == num[i]){

????????????????????????????return num[i];

? ? ? ? ? ? ? ????????? }else{

????????????????????????????int tem = num[i];

? ? ? ? ? ? ? ? ? ????????? num[i] = num[num[i]];

? ? ? ? ? ? ? ? ? ????????? num[tem] = tem;

? ? ? ? ? ? ? ????????? }

????????????????????}

? ? ? ? ? ? ? ? ? ? ? i++;

? ? ? ????????? }

????????????return -1;

? ????? }

? ?}