LeetCode日记–26.移除排序数组中的重复字符

发布于 2020-09-16  133 次阅读


昨儿发烧到38.5℃,还以为要被校医院拉去隔离了,幸亏没有。今天补上前天写的题。

题目如下:

Given a sorted array "nums", remove the duplicates in-place such that each element appears 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.

Example 1:

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.

Example 2:

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.


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:

// 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]);
}

本人彩笔思路:

用一个哈希表存储遍历中已经出现过的字符,遍历时查询哈希表可以知道字符串是否已经出现过了。最后把哈希表中的值存到一个数组中返回。

复杂度分析:

时间复杂度可以认为是O(n),但是空间复杂度完全没有达到要求的O(1)。

官方题解:

使用双指针。注意,这里的双指针与第十一题:《盛水最多的容器》中两头向内搜索的指针(用于降低遍历的时间复杂度)不同。

本题中的双指针分为快慢两个指针。其中快指针用于遍历nums数组,慢指针用于把找到的第一次出现的字符放到前面(为了保证空间复杂度为O(1))。

动图演示:来自GitHub项目“LeetCodeAnimation”

复杂度分析:

显然时间复杂度为O(n),空间复杂度也达到了O(1)的要求。

代码如下:

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length==0)
            return 0;
        int leftPointer=0;
        int rightPointer=1;
        // int intermediateVariable=0;
        for(;rightPointer<nums.length;rightPointer++){
            if(nums[rightPointer]!=nums[leftPointer]){
                // intermediateVariable = nums[rightPointer];
                // nums[rightPointer] = nums[leftPointer];
                nums[leftPointer+1] = nums[rightPointer];
                leftPointer++;
            }
        }
            
        return leftPointer+1;
    }
}

你好哇!欢迎来到雷公马碎碎念的地方:)