leetcode - [26] Remove Duplicates from Sorted Array

2020/07/17

问题描述

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

给你一个有序数组,将数组中第一次出现的元素从头往后排列,并返回其长度。

举个例子:

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.

解法1

Thanks [Y总]

典型的双指针问题。

核心在于找到所有第一次出现的所有元素,那么如何找?

使用一个指针i从头到尾遍历整个数组,如果当前元素前一个元素不相等,

那么当前元素就是第一次出现的元素,因为数组是升序排列的。

然后,再用一个指针j代表截止至唯一元素的边界。

最后,非常巧妙,j就是要求的长度。

来看下整体流程:

注意,第一个元素特判一下。

来看下实现:

class Solution {
    public int removeDuplicates(int[] nums) {
    
        int n = nums.length;
        int j = 0;
        for (int i = 0; i < n; i++){
            if (i == 0 || nums[i] != nums[i - 1]){
                nums[j++] = nums[i];
            }
        }
        return j; 
    }
}

Enjoy it !


一位喜欢提问、尝试的程序员

(转载本站文章请注明作者和出处 姚屹晨-yaoyichen

Post Directory