[LeetCode] 26. Remove Duplicates from Sorted Array

发表于 Disqus：

LeetCode 26. Remove Duplicates from Sorted Array (删除排序数组中的重复项) Diffculty: Eazy

Question

Given a sorted array nums, 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 by modifying the input array in-place with $O(1)$ extra memory.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

1
2
3
4
5
6
7
8
// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

给定一个排序数组 nums，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 $O(1)$ 额外空间的条件下完成。

说明：

为什么返回数值是整数，但输出的答案是数组呢？

请注意，输入数组是以”引用“方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下：

1
2
3
4
5
6
7
8
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度，它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

Example

Example 1

1
2
3
4
5
6
7
8
Given nums = [1,1,2],
给定数组 nums = [1,1,2], 

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 

It doesn't matter what you leave beyond the returned length.
你不需要考虑数组中超出新长度后面的元素。

Example 2

1
2
3
4
5
6
7
8
Given nums = [0,0,1,1,1,2,2,3,3,4],
给定 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.
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

It doesn't matter what values are set beyond the returned length.
你不需要考虑数组中超出新长度后面的元素。

Solution

Java

My Solution 1

老实说，我没做出来。

说说我的思路。

首先理解题意：

  1. nums 是一个排序数组
  2. 在原地删除重复出现的元素。即不能使用另外的数组去接收剔除重复后的元素
  3. 使得每个元素只出现一次，返回移除后数组的新长度。即去重后，返回数组的新长度

我有两种思路：

  1. 从索引 0 开始（外循环）
  2. 将获得的元素，与之后的元素依次比对，然后将最后一个重复的元素的索引 +1，获得下一个不重复的元素。（如，比对元素的索引为 0，最后一个重复元素的索引为 2，则下一个不重复的元素索引为 2 + 1 = 3）（内循环）
  3. 再将下一个不重复的元素，与当前获得的元素的索引 +1，进行调换。（如，将索引 3，与索引 1，进行调换）
  4. 最后结果，调换次数 +1

还有种思路和上面的差不多，只是调换方式不一样，是将重复元素往后面放。

即，一种是遇到重复的元素就将非重复的放到前面，然后重复的元素后退一位。第二种是遇到重复的元素就将重复元素放到最后面。

虽然最后写出来，没有通过 Testcase。我觉得这样应该是可行的，只是有点麻烦，操作和边界处理有点多。

LeetCode Solution 1: Two Pointers

Since the array is already sorted, we can keep two pointers i and j, where i is the slow-runner while j is the fast-runner. As long as nums[i] = nums[j], we increment j to skip the duplicate.

When we encounter nums[j] != nums[i], the duplicate run has ended so we must copy its value to nums[i + 1]. i is then incremented and we repeat the same process again until j reaches the end of array.

数组完成排序后，我们可以放置两个指针 i 和 j，其中 i 是慢指针，而 j 是快指针。只要 nums[i] = nums[j]，我们就增加 j 以跳过重复项。

当我们遇到 nums[j] != nums[i] 时，跳过重复项的运行已经结束，因此我们必须把它（nums[j]）的值复制到 nums[i + 1]。然后递增 i，接着我们将再次重复相同的过程，直到 j 到达数组的末尾为止。

Code
1
2
3
4
5
6
7
8
9
10
11
public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int i = 0;
    for (int j = 1; j < nums.length; j++) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}
Complexity Analysis
  • 时间复杂度：$O(n)$，假设数组的长度是 n，那么 i 和 j 分别最多遍历 n 步。
  • 空间复杂度：$O(1)$。

LeetCode Discuss Solution 1

5 lines Java solution

Code @annafan
1
2
3
4
5
6
7
8
9
public int removeDuplicates(int[] A) {
    if (A.length == 0)
        return 0;
    int j = 0;
    for (int i = 0; i < A.length; i++)
        if (A[i] != A[j])
            A[++j] = A[i];
    return ++j;
}
Complexity Analysis
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$

LeetCode Discuss Solution 2

5 lines C++/Java, nicer loops

Code @StefanPochmann
1
2
3
4
5
6
7
public int removeDuplicates(int[] nums) {
    int i = 0;
    for (int n : nums)
        if (i == 0 || n > nums[i - 1])
            nums[i++] = n;
    return i;
}
1
2
3
4
5
6
7
public int removeDuplicates(int[] nums) {
    int i = nums.length > 0 ? 1 : 0;
    for (int n : nums)
        if (n > nums[i - 1])
            nums[i++] = n;
    return i;
}
Complexity Analysis
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$

Summary

两周没做过算法题，就感觉蠢了，也有可能本来就蠢，这下更蠢了。😣

双指针 和 单指针 都好 6 啊。什么时候才能像他们一样优秀。

思路和我想的差不多，但是我竟然没有短时间内做出来，写出来的代码也长，路漫漫其修远兮啊。

References