我們可以照之前的 pattern,先做完 cyclic sort,然後再找出跟 index 對不上的 element,那個 element 就是 duplicate 的 number。
classSolution {public:intfindDuplicate(vector<int>& nums) { // Cyclic sortint i =0, n =nums.size();while(i < n) {int j =nums[i] -1;if(j < n andnums[i] !=nums[j]) {swap(nums[i],nums[j]); }else{++i; } } // If the number do not match the index, that's the duplicate numberint duplicate;for(int i =0; i < n; ++i) {if(nums[i] != i +1) { duplicate =nums[i];break; } }return duplicate; }};