引言
题目链接：https://leetcode.com/problems/remove-duplicates-from-sorted-array/
题目大意
给定排序的数组nums，就地删除重复项，使每个元素只出现一次并返回新的长度。
Hint：不要为另一个数组分配额外的空间，必须通过使用O(1)额外内存修改输入数组来实现此目的。
- Example
|
1 2 3 4 5 6 7 |
Given nums = [1,1,2], Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the returned length. Given nums = [0,0,1,1,1,2,2,3,3,4], Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively. It doesn't matter what values are set beyond the returned length. |
题解
一句话题解：O(1)空间复杂度要求，即利用原数组，顺序遍历数组，把不重复的项放在数组头部即可。维持一个index用于存储下标，直接顺序遍历，找到数组当前数据与前一个数据不一致即出现一个新数字，放在当前index+1的位置即可。
复杂度
时间复杂度 O(n)
空间复杂度 O(1)
AC代码
c++版本
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Solution { public: int removeDuplicates(vector<int> &nums) { if (nums.empty()) { return 0; } int ret = 1; int index = 1; for (int i = 1; i < nums.size(); ++i) { if (nums[i] != nums[i - 1]) { ++ret; nums[index++] = nums[i]; } } return ret; } }; |
go版本
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
func removeDuplicates(nums []int) int { lens := len(nums) if 0 == lens { return 0 } ret, index := 1, 1 for i := 1; i < lens; i++ { if nums[i] != nums[i-1] { ret++ nums[index] = nums[i] index++ } } return ret } |
