## 一.題目描述  ## 二.解題技巧 這道題和Remove Duplicates from Sorted Array這道題是類似的，只不過這里允許出現重復的數字而已，可以采用二分搜索的變種算法，只不過加入了剔除和第一個元素相同的元素的過程。 另一個思路是加入一個變量，用于記錄元素出現的次數。這題因為是已經排序的數組，所以一個變量即可解決。如果是沒有排序的數組，則需要引入一個hash表來記錄出現次數。 ## 三.示例代碼 ~~~ #include <iostream> #include <vector> class Solution { public: int RemoveDuplicatesII(int A[], int n, int dupNum) // dupNum為允許重復的次數 { if (n < (dupNum + 1)) return n; // 數組元素過少，無需刪除重復數據 int num = dupNum; // 存放刪除后數組的元素個數，至少有2個元素 for (int i = dupNum; i < n; i++) { if (A[i] != A[num - dupNum]) { A[num++] = A[i]; // 使用不重復元素替換第num個元素的位置 } } // 執行算法后，數組A的前num個元素是所求的一個集合 return num; } }; ~~~ 測試代碼： ~~~ #include <algorithm> #include "solution.h" using namespace std; int main() { int removeTime = 2; // 允許數組中每個元素最多重復的次數 int a[100]; // 定義一個存放100個元素的數組 int n = 100; for (int i = 0; i < n; i++) a[i] = rand() % 10 - 5; sort(a, a + 100); // 要求在執行算法之前數組已經過排序 cout << "原始數組："; for (int j = 0; j < n; j++) cout << a[j] << " "; cout << endl << endl; Solution remove; int result_num; result_num = remove.RemoveDuplicatesII(a, n, removeTime); for (int k = 0; k < result_num; k++) // 數組a中前result_num個元素是處理后的元素 cout << a[k] << " "; cout << endl; cout << "刪除重復多于" << removeTime << "次的數據后數組剩余" << result_num << "個元素" << endl; getchar(); return 0; } ~~~ 一個測試結果：  該方法有一定的擴展性，允許元素重復若干次，如以下情況元素允許重復最多5次：  另一種使用二分查找的方法： ~~~ class Solution { public: int RemoveDuplicatesFromStart(int* A, int n) { int NumberOfDuplicates = 0; int Start = A[0]; for (int Index = 1; Index < n; Index++) { if ( Start != A[Index]) { break; } NumberOfDuplicates++; } return NumberOfDuplicates; } int RemoveDuplicatesFromEnd(int* A, int n) { int NumberOfDuplicates = 0; int Start = A[0]; for (int Index = n - 1; Index > 0; Index--) { if (Start != A[Index]) { break; } NumberOfDuplicates++; } return NumberOfDuplicates; } bool search(int A[], int n, int target) { if (n < 1) { return false; } if (n == 1) { if (A[0] == target) { return true; } return false; } if (n == 2) { if (A[0] == target) { return true; } if (A[1] == target) { return true; } return false; } if (A[0] == target) { return true; } // remove the duplicates int DuplicatesFromStart = RemoveDuplicatesFromStart(A, n); if (DuplicatesFromStart == (n - 1)) { return false; } int DuplicatesFromEnd = RemoveDuplicatesFromEnd(A, n); if (DuplicatesFromEnd == (n - 1)) { return false; } n = n - DuplicatesFromStart - DuplicatesFromEnd; if (n < 2) { return false; } A = A + DuplicatesFromStart; if (A[n / 2] == target) { return true; } if (A[0] > target) { if (A[0] < A[n / 2]) { return search((A + n / 2), (n - n / 2 ), target); } if (A[n / 2] < target) { return search((A + n / 2), (n - n / 2), target); } return search(A, (n / 2), target); } else { if (A[0] < A[n / 2]) { if (A[n / 2] < target) { return search((A + n / 2), (n - n / 2), target); } return search(A, (n / 2), target); } return search(A, (n / 2), target); } } }; ~~~ ## 四.體會 第一種方法的時間復雜度O(n)，空間復雜度O(1)，支持in place運算，同時有一定的擴展性。 若采用變種的二分搜索算法，事實上則是加入了剔除和第一個元素相同的元素的過程，加入了這個過程之后，此時在最差情況下的時間復雜度為O(n)。