算法系列之数组里的双指针

算法系列之数组里的双指针

在数组和链表的算法中双指针常出现,这篇用两道题来看一下双指针在数组算法里的用处。

快慢指针代替双重循环

https://leetcode.cn/problems/remove-element/description/

题目:
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例:
输入:nums = [3,2,2,3], val = 3
输出:2, nums = [2,2]
解释:函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如,函数返回的新长度为 2 ,而 nums = [2,2,3,3] 或 nums = [2,2,0,0],也会被视作正确答案。

输入:nums = [0,1,2,2,3,0,4,2], val = 2
输出:5, nums = [0,1,3,0,4]
解释:函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

暴力解法

首先直接想暴力解法,因为题目中明说了我们不可以创建新的数组,所以我们考虑对数组本身做删除。又因为数组是连续存储空间,我们在删除一个数后,需要把它后面的都往前挪一个。这就很明显需要双重循环,也就是 O(n^2) 的时间复杂度。代码如下:

var removeElement = function(nums, val) {
    let valCount = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === val && i + valCount < nums.length) { 
            valCount ++;
            for (let j = i; j < nums.length - 1; j++) {
                nums[j] = nums[j + 1];
            }
            i --; // 因为 i 后面的数都往前移了一位,i 也有新的数代替了,所以 i 这个位置也要重新判断。
        }
    }
    return nums.length - valCount; // 这里不用 valCount 也可以每次进入判断直接把数组后面的数 pop 出去,直接缩小数组。(用 pop 比这种方法更耗时)
}

快慢指针法

可不可以变成 O(n) 的时间复杂度,也就是一遍循环搞定呢。这里就可以巧用快慢指针的思想。
快指针每次向后移动一位,判断当前值是不是要排除的值。

  • 是排除值则慢指针不变,快指针继续往后移动。
  • 不是排除值说明要保留,就放到慢指针指向的位置,慢指针也往后移动一位。

这样可以保证慢指针范围内的都是需要保留的数组。

var removeElement = function(nums, val) {
    let lIndex = 0, rIndex = 0;
    while(rIndex < nums.length) {
        if (nums[rIndex] !== val) {
            nums[lIndex++] = nums[rIndex++];
        } else {
            rIndex ++;
        }
    }
    return lIndex;
};

在这里插入图片描述

用双指针来排序

https://leetcode.cn/problems/squares-of-a-sorted-array/description/

题目:
给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。

示例:
输入:nums = [-4,-1,0,3,10]
输出:[0,1,9,16,100]
解释:平方后,数组变为 [16,1,0,9,100]
排序后,数组变为 [0,1,9,16,100]

输入:nums = [-7,-3,2,3,11]
输出:[4,9,9,49,121]

暴力解法

先平方,再进行排序,sort底层是快排,所以时间复杂度是 O(n + nlogn)

function sortedSquares(nums: number[]): number[] {
    return nums.map((item: number) => item * item).sort((a, b) => a - b);
};

双指针排序

暴力解法没有用到本来就是排序数组这个特点。因为本来排序过,所以最大的肯定在两端,约往中间越小,我们定义两个指针从左右边界开始往内部移动,移动中比较左右哪个的平方比较大就先加入结果数组并进行移动。
只进行了一次遍历,时间复杂度是 O(n)。

function sortedSquares(nums: number[]): number[] {
    const res = [];
    let lIndex = 0, rIndex = nums.length - 1;
    while (lIndex !== rIndex) {
        if (nums[lIndex] ** 2 < nums[rIndex] ** 2) {
            res.unshift(nums[rIndex] ** 2);
            rIndex --;
        } else {
            res.unshift(nums[lIndex] ** 2);
            lIndex ++;
        }
    }
    res.unshift(nums[lIndex] ** 2);
    return res;
};

在这里插入图片描述

相关推荐

  1. 指针 有效三角形个数

    2024-03-29 22:38:02       64 阅读
  2. 算法:删除有序数组重复项---指针[3]

    2024-03-29 22:38:02       59 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-03-29 22:38:02       94 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-03-29 22:38:02       100 阅读
  3. 在Django里面运行非项目文件

    2024-03-29 22:38:02       82 阅读
  4. Python语言-面向对象

    2024-03-29 22:38:02       91 阅读

热门阅读

  1. 【python学习】基础篇-命名规范

    2024-03-29 22:38:02       41 阅读
  2. 项目中线程池的应用

    2024-03-29 22:38:02       54 阅读
  3. Pandas合并数据集

    2024-03-29 22:38:02       35 阅读
  4. 每日一题(leetcode2909):单份查找与群组查找

    2024-03-29 22:38:02       43 阅读
  5. nginx符号链接介绍

    2024-03-29 22:38:02       33 阅读
  6. 【WPF应用22】WPF 中的 PasswordBox 控件详解

    2024-03-29 22:38:02       37 阅读