导航
导航
文章目录
  1. 题目
  2. 翻译

LeetCode-26.Remove Duplicates from Sorted Array

题目

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array 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 new length.

翻译

给出一个有序数组,原地移除其中的重复元素,确保每个元素只出现一次,返回新的长度。
不要申请额外空间新建数组,必须用常数内存原地完成操作。
例如,
给出输入数据 nums = [1,1,2],
你的函数应当返回 length = 2,nums的第一个和第二个元素应当分别为1和2。剩下的元素无所谓。

类似283.Move Zeroes和27.Remove Element,设立两个指针,一个不断向后扫,一个记录新数组长度,因为是有序数组,所以只要判断大小即可得出新数组中是否已存在:

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
public int removeDuplicates(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
int newLen = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1])
nums[newLen++] = nums[i];
}
return newLen;
}
}

另外,如果给出的是普通数组,则可先排序,再应用以上方法;如果可以利用额外空间,则可设立一个HashSet,记录已存在的数字:

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public int removeDuplicates(int[] nums) {
Set<Integer> newNums = new HashSet<Integer>();
int newLen = 0;
for (int i = 0; i < nums.length; i++) {
if (!newNums.contains(nums[i])) {
nums[newLen++] = nums[i];
newNums.add(nums[i]);
}
}
return newLen;
}
}