## 一.題目描述  ## 二.解題技巧 從題目中可知，數組中的元素事先已經過排序，因此一個簡單而易于實現的方法是從第二個元素開始對數組元素進行遍歷，并判斷該元素是否和前面的元素相同。題目要求返回不重復的元素的個數。 算法的一個要求是：返回的數組的元素都是不重復，同時要求remove duplicates in place，這意味著不能重新定義一個數組來保存不重復的元素。假設該數組為A，為了滿足這一要求，可以設置一個變量num來保存不重復的元素的個數，然后遍歷整個數組A，如果該元素A[i]!=A[i-1]的話，將第i個元素復制到A的num位置，也即是A[num]=A[i],然后將num加1. 主要的注意點是，如果數組的元素個數小于2的話，就可以提前結束函數了。 ## 三.示例代碼 ~~~ #include <iostream> using namespace std; class Solution { public: int removeDuplicates(int A[], int n) { if (n < 2) return 0; // 數組元素個數小于2時無需執行算法 int num = 0; for (int i = 1; i < n; i++) { if (A[num] != A[i]) A[++num] = A[i]; } return num + 1; } }; ~~~ 測試代碼： ~~~ #include "solution.h" #include <algorithm> int main() { int num = 50; int number[50]; for (int i = 0; i < num; i++) number[i] = rand() % 10 - 10; sort(number, number + num); // 先對數組進行排序 cout << "輸入的數組（已排序）：" << endl; for (int j = 0; j < num; j++) cout << number[j] << " "; cout << endl << endl; Solution remove; int index = remove.removeDuplicates(number, num); // 執行算法 cout << "去除重復元素后的數組：" << endl; for (int k = 0; k <index; k++) cout << number[k] << " "; cout << endl; cout << "數組元素的剩余個數：" << index << endl; getchar(); return 0; } ~~~ 一個輸出結果：  **網上一種使用STL的解決思路如下：** ~~~ // 算法的時間復雜度O(n)，空間復雜度O(1) class Solution { public: int removeDuplicates(int A[], int n) { return removeDuplicates(A, A + n, A) - A; } template<typename InIt, typename OutIt> OutIt removeDuplicates(InIt first, InIt last, OutIt output) { while (first != last) { *output++ = *first; first = upper_bound(first, last, *first); } return output; } }; ~~~ ## 四.體會 這道題本身無需排序，只需判斷元素與前一個元素是否相同就知道該元素是不是重復的，同時，記錄已經遍歷過的元素中不重復的元素的個數的變量也同時記錄了下一個不重復的元素在數組中的存放位置。算法實現較為簡單，當然，可能存在其他更簡單的思路。