Description:
Given an array of integers, remove the duplicate numbers in it.
You should:
- Do it in place in the array.
- Move the unique numbers to the front of the array.
- Return the total number of the unique numbers.
Example:
Given nums = [1,3,1,4,4,2], you should:
Move duplicate integers to the tail of nums => nums = [1,3,4,2,?,?].
Return the number of unique integers in nums => 4.
Actually we don't care about what you place in ?, we only care about the part which has no duplicate integers.
Link:
http://www.lintcode.com/en/problem/remove-duplicate-numbers-in-array/
解題思路：
這道題意思是去除數(shù)組中的重復(fù)數(shù)字骤铃，并且把不重復(fù)的數(shù)字移動到數(shù)組前面挨务，并且返回不重復(fù)數(shù)字的個數(shù)秉继。
要求do it in place in the array, 也就是在O(n)的空間內(nèi)完成。
解題方法：
所以解題方法有2中：
1）O(n)時間穿剖，O(n)空間：用哈希表去重，再把哈希表里的元素重新放進數(shù)組里面佑笋，記錄數(shù)量寄狼。
2）O(nlogn)時間，O(1)空間：首先對數(shù)組排序柑营，然后用快慢指針解決屈雄，快慢指針在同一起點，因為已經(jīng)排序所以重復(fù)數(shù)字會排在一起官套，所以快指針一個個讀取數(shù)字酒奶，每當(dāng)讀到與慢指針不同的數(shù)字，慢指針首先往后走一格（保存之前的數(shù)）奶赔，然后再把快指針所在的數(shù)放到慢指針的位置（獲得到新的數(shù)）惋嚎。不停重復(fù)這個過程直到快指針走完數(shù)組。慢指針所在的位置就是最后一個unique number的位置站刑。
Tips:
nums[++count] = nums[i];
Time Complexity：
方法1：O(n)時間 O(n)空間
方法2：O(nlogn)時間 O(1)空間
完整代碼：
方法1
int count = 0; if(nums.size() == 0) return count; unordered_map <int, bool> maps; for(int i : nums) maps[i] = true; for(auto a : maps) nums[count++] = a.first; return count;
方法2
int count = 0; if(nums.size() == 0) return count; sort(nums.begin(), nums.end()); for(int i = 0; i < nums.size(); i++) { if(nums[i] != nums[count]) nums[++count] = nums[i]; } return count+1;
