LeetCode 80 Remove Duplicates from Sorted Array II

题意

给定一个数组,删除其中的重复元素,使重复项最多出现两次,然后返回新的长度,要求 O(1) 空间复杂度。

例 1:

1
2
3
给予 nums = [1, 1, 1, 2, 2, 3],

你的函数应该返回 length = 5,前五个元素分别为 1, 1, 2, 2, 3.

例 2:

1
2
3
给予 nums = [0, 0, 1, 1, 1, 1, 2, 3, 3],

你的函数应该返回 length = 7,前五个元素分别为 0, 0, 1, 1, 2, 3, 3.

解法

LeetCode 26 Remove Duplicates from Sorted Array 这道题比较类似。
定义变量 k,表示待修改的元素位置,默认为 0,然后遍历后面的元素判断符合条件时,覆盖 k,然后 k 向后移动一位。
判断条件为:

  • 遍历的元素 n 不等于元素 k,也就代表不重复
  • 遍历的元素 n 等于元素 k,但不等于 k - 1。则表示已经有两个重复元素了
  • 对于第二点,需要注意,当 k = 0 时,没有 k - 1。
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public int removeDuplicates(int[] nums) {
int k = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i] != nums[k] || k == 0 || (nums[i] == nums[k] && nums[i] != nums[k - 1])) {
nums[++k] = nums[i];
}
}
return k + 1;
}
}

Runtime: 6 ms, faster than 95.36% of Java online submissions for Remove Duplicates from Sorted Array II.

  • 本文作者: 赵俊
  • 本文链接: http://www.zhaojun.im/leetcode-80/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!