问题链接
LeetCode 26. Remove Duplicates from Sorted Array
题目解析
给定有序数组，删除其中重复元素，返回新数组长度。
解题思路
由于不是很懂题目的意思，题目要求不要分配额外的数组空间，其实是想说保证空间复杂度为 \(O(1)\)。
简单题。了解一下，std::unique。unique函数要求有序数组，需要注意的是unique函数并不是真正地把元素删除，而是将重复的元素移动到最后了，该函数返回最后一个非重复元素的下一位置。所以，使用unique函数后，再用erase函数删除元素。
参考代码
class Solution {
public:int removeDuplicates(vector<int>& nums) {nums.erase(unique(nums.begin(), nums.end()), nums.end());return nums.size();}
};快慢指针
使用快慢指针（cur & pre）来记录遍历的坐标，初始两个指针都指向第一个数字，如果两个指针指的数字相同，则快指针+1；如果不同，则两个指针都+1。当快指针到达数组尾部，慢指针当前的坐标加1就是数组中不同数字的个数。参考代码如下：
class Solution {
public:int removeDuplicates(vector<int>& nums) {if (nums.empty()) return 0;int pre = 0, cur = 0, len = nums.size();while (cur < len) {if (nums[pre] == nums[cur]) ++cur;else nums[++pre] = nums[cur++];}return pre + 1;}
};官方解法
官方链接：https://leetcode.com/problems/remove-duplicates-from-sorted-array/solution/。
其实官方解法就是上面的快慢指针，其中 \(i\) 就是 \(pre\)，\(j\) 就是 \(cur\)。
class Solution {
public:int removeDuplicates(vector<int>& nums) {if (nums.empty()) return 0;int j = 0, n = nums.size();for (int i = 0; i < n; ++i) {if (nums[i] != nums[j]) nums[++j] = nums[i];}return j + 1;}
};LeetCode All in One题解汇总（持续更新中...）
本文版权归作者AlvinZH和博客园所有，欢迎转载和商用，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利.