重复数字

 1 // 令m = arr.size(), 且m >= n.
 2 // arr中保存着[0, n)的数字, 由于m >= n, 之中必然有重复的.
 3 // 输出他们.
 4 void PrintDuplicateNumbers(vector<int>& arr, int n)  {
 5     for (int i = 0; i < arr.size(); ++i) {
 6         int current = arr[i];
 7         if(current == i)
 8             continue;
 9 
10         // 希望交换的位置上的值与自身相同, 表明自身是多余值.
11         if (arr[current] == current) {
12             cout << arr[current] << " ";
13             continue;
14         }
15 
16         swap(arr[current], arr[i]);
17 
18         // [0, i)之间的值, 或者处于正确的位置, 或者它正确的位置被其他相同的值占领.
19         // 如果current < i, 表明是向前的一次交换, 且交换的一定是上述第二种情况的
20         // 值. 而该值已经是多余的, 因此无需再继续检查该位置.
21         if (current > i)
22             --i;
23     }
24 }