leetcode Binary Search

leetcode 26题

Posted by franki on November 24, 2020

leetcode 26题 删除排序数组中的重复项

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

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

示例 1

给定数组 nums = [1,1,2],

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。

你不需要考虑数组中超出新长度后面的元素。

示例 2

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

思路

1 双指针用法，利用左右指针，左指针从0开始，右指针从1开始，比较左右指针对应的值，如果相等，则删除当前left对应的值，直到right < 数组的长度不满足。返回当前数组的长度。

2 快慢指针，利用快指针一直前进，当快慢指针对应的值不相等的时候，满指针前进一步，并且把快指针的值复制给满指针对应的值，直到循环结束

代码

function removeDuplicates(nums) {
    var left = 0, right = 1;
    while (right < nums.length) {
        if (nums[left] === nums[right]) {
            nums.splice(left, 1);
        } else {
            left++;
            right++;
        }
    }
    return nums.length;
}

var removeDuplicates = function(nums) {
    // 快慢指针
    if (nums.length === 0) return 0;
    let i = 0;
    for (let j=0; j<nums.length; j++) {
        if (nums[i] !== nums[j]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i+1;
};

复杂度分析

  • 时间复杂度: O(n)
  • 空间复杂度: O(1)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python
    FRIENDS