美文网首页程序员
力扣 26 删除排序数组中的重复项

力扣 26 删除排序数组中的重复项

作者: zhaojinhui | 来源:发表于2020-07-15 11:07 被阅读0次

题意:给定一个有序数组,返回去重后的数组

思路:

  1. 定义一个end指针和runner指针,指向开头,end指向当前数组最后一个合法的数的index,runner指向当前遍历到的数的index
  2. 遍历数组
    1. 当runner指针和end指针指向的数相同时,后移runner
    2. 当runner指针和end指针指向的数不同时,后移end指针,并用runner当前的数更新end,并后移runner
  3. 返回end+1,因为end是index,数组长度是index+1

思想:快慢指针

复杂度:时间O(n),空间O(1)

class Solution {
    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        int end = 0;
        int runner = 0;
        for(int i=0;i<len;i++) {
            if(nums[end] == nums[runner]) {
                runner++;
            } else {
                nums[++end] = nums[runner++];
            }
        }
        return end+1;
    }
}

相关文章

网友评论

    本文标题:力扣 26 删除排序数组中的重复项

    本文链接:https://www.haomeiwen.com/subject/cgrdhktx.html