数组排序去重

摘要：
一个快速实现数组排序去重的小技巧。

为什么要记录这个呢，因为算法题中经常用到。

C++

1. 用sort函数配合STL的unique函数实现：

   #include <algorithm>
   vector<int> nums;
   sort(nums.begin(), nums.end());                                 // 1
   nums.erase(unique(nums.begin(), nums.end()), nums.end());       // 2

   • 1. 将原数组排序
   • 2. unique函数实现将数组相邻数中重复的移动到函数尾端，返回包含所有重复数字的数组段的起始位置。
        接下来用erase函数将重复段擦除。

2. 自己造轮子
   维护两个指针i和j，i负责遍历数组，比较每一项与上一项；j负责指向存储不重复元素的位置。当i遇到不重复项时，j跟随i移动；否则j停止，等待i遇到下一个不重复项。

   vector<int>::iterator unique(vector<int> &a) 
   {
       int j = 0;
       for (int i = 0; i < a.size(); i ++ ) {
           if (!i || a[i] != a[i - 1]) {                     // 1
               a[j ++] = a[i];                               // 2
           }
       }
       // unique between 0 and j - 1
       return a.begin() + j;
   }

   • 1. !i等价于i == 0。当i取首位或者a[i]与上一位相等时，说明a[i]是不重复元素。
   • 2. 这里体现了 原地算法思想（in-place algorithm）。一旦i超过首位且a[i] == a[i - 1]（遇到重复情况），j指针会停留在重复位置，等待i指针找到下一个不重复元素, 直接将不重复元素覆盖掉j指针指向的重复位置。

Java

用到再来写.