LeetCode - 26 - 删除有序数组的重复项 - java - 细喔

x33g5p2x  于2022-02-07 转载在 Java  
字(1.0k)|赞(0)|评价(0)|浏览(204)

题目

题目解析

给我们一个有序数组【升序:相同的元素是紧挨着的】,让我们找到 数组中不重复的元素,将其安照原来的规则,排序在数组开头部分,
题目中的 “删除”,不需要我们去在意,纯属干扰条件!因为我们可以从示例解释中看到

我们只需要 将 不同的元素,按照升序的规则,摆放在数组开头的位置。就欧克了。
至于返回值,也就是 不同元素的个数。

解题思维

利用 双指针来解决该问题。
定义 两个整形指针 fast 和 slow,并初始化为 1.因为数组不为长度不为0,说明至少有一个元素,

3个目的:
目的一: slow 用来表示 不同元素的个数,即:“删除元素后 数组的长度”。另外,数组不为空,至少有一个元素,这个元素就是 nums[0]。此时,我们的slow是 1,即:nums[slow] == nums[1],你可以理解为我们在为下一个不同元素标记好它该去的位置。

目的二: fast 用来比较两个元素是否相同。

目的三: fast 和 slow 初始化为1,用来表示数组下标

下面就是重点:因为 fast 的值,表示下标为 fast 的 元素,我们只需要去判断 与上一个元素【fast-1】是否相等。
如果不相等:说明 下标 fast-1 和 fast 的元素 为 两个不同元素。nums[slow] = nums[fast]。然后,slow加加,为下一个不同元素做准备,
反之,如果相等: 说明是 下标 fast-1 和 fast 的元素 为 两个相同元素,我们将让fast 继续往后走,slow不动!
直到 fast 与 fast-1 不同,执行 nums[slow] = nums[fast],slow加加,为下一个不同元素做准备,。 或者,fast == n 跳出循环(避免越界异常)【脑子灵活点:这是一个升序数组(相同的元素是紧挨着的),而且我们是两两一比,还是紧挨着的两个比较,所以不要想太多!这就是一类人站一起,有一个不同的,是很容易观察到的。】

代码如下

class Solution {
    public int removeDuplicates(int[] nums) { 
        int n = nums.length;
        if(n == 0){
            return n;
        }
        int fast = 1;
        int slow = 1;
        while(fast < n){
            if(nums[fast] != nums[fast-1]){
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }
}

相关文章

微信公众号

最新文章

更多