題目描述

在一個長度為n的數組里的所有數字都在0到n-1的范圍內。 數組中某些數字是重復的，但不知道有幾個數字是重復的。也不知道每個數字重復幾次。請找出數組中任意一個重復的數字。 例如，如果輸入長度為7的數組{2,3,1,0,2,5,3}，那么對應的輸出是第一個重復的數字2。

解題思路

掃描數組{2,3,1,0,2,5,3}下標為0開始，如果當前位置的數不等于它的下標則與下表為當前元素的值進行交換

1. 第一次，下標為0，值為2.不等于，與下標為2的數字1進行交換{1,3,2,0,2,5,3}
2. 第二次，下標為0，值為1，不等于，與下標為1的數字3進行交換{3,1,2,0,2,5,3}
3. 第三次，下標為0，值為3，不等于，與下標為3的數字0進行交換{0,1,2,3,2,5,3}
4. 第四次，下標為0，值為0，等于，判斷下一個{1,2,3,2,5,3}
5. 第五次，下標為1，值為1，等于，判斷下一個{2,3,2,5,3}
6. 第六次，下擺為2，值為2，等于，判斷下一個{3,2,5,3}
7. 第七次，下標為3，值為3，等于，判斷下一格{2,5,3}
8. 第八次，下標為4，值為2，不等于，與下標為2數字進行交換，此時下標為2的數字為2，所以第一個重復的數字找到

代碼實現

class Solution {
public:// Parameters://        numbers:     an array of integers//        length:      the length of array numbers//        duplication: (Output) the duplicated number in the array number// Return value:       true if the input is valid, and there are some duplications in the array number//                     otherwise falsebool duplicate(int numbers[], int length, int* duplication) {if(numbers == nullptr || length <= 0)return false;for(int i=0;i<length;++i){if(numbers[i]<0 || numbers[i]>length-1)return false;}for(int i=0;i<length;++i){while(numbers[i] != i){if(numbers[i] == numbers[numbers[i]]){*duplication = numbers[i];return true;}swap(numbers[i],numbers[numbers[i]]);}}return false;}
};