xicheng

V1

2022/06/24阅读:14主题:默认主题

数组-一口气冲完快慢指针

前言

  上篇文章讲了差分数组,这篇文章开始讲双指针技巧的快慢指针技巧。另外,数组有下图这些知识点与技巧。

思路

  通过两个指针来操作数组,通常应用在:1.对数组有更改且不能建立新数组的情况下。2.一遍历实现需求。
  另外,双指针类型有快慢指针,左右指针,滑动窗户,普通类型。
快慢指针模板

int 慢指针 = 0;
for (int 快指针 = 0; fast < nums.length; 快指针++) {
    if (快指针满足某个条件) {
        慢指针赋值操作
        慢指针右移动操作
    }
}

删除有序数组中的重复项

leetcode第26题 解题思路
  套用模板,“快指针满足某个条件中的条件”:指快慢指针所指的元素不同。   最后返回值时,需要将慢指针+1。
复杂度分析
  时间复杂度:O(n),n是数组的长度。   空间复杂度:O(1)。
代码

class Solution {
    public int removeDuplicates(int[] nums) {
      int slow = 0;
      for (int fast = 0; fast < nums.length; fast++) {
         //快慢指针所指元素不通
         if (nums[fast] != nums[slow]) {
            nums[++slow] = nums[fast];
         }
      }
      return slow + 1;
    }
}

移除元素

leetcode第27题 解题思路
  套用模板,“快指针满足某个条件中的条件”:指快指针所指的元素与给定值不同。
复杂度分析
  时间复杂度:O(n),n是数组的长度。
  空间复杂度:O(1)。
代码

class Solution {
    public int removeElement(int[] nums, int val) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            //快指针所指元素与val不同
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
}

移动零

leetcode第283题 解题思路
  套用模板,“快指针满足某个条件中的条件”:指快指针所指的元素不等于0。
  最后从在慢指针往后遍历数组,将遍历到的元素都赋值为0。
复杂度分析
  时间复杂度:O(n),n是数组的长度。
  空间复杂度:O(1)。
代码

class Solution {
    public void moveZeroes(int[] nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != 0) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        //将满指针及后面的位置都赋值为0
        for (int i = slow; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}

结尾

  数组的快慢指针比较简单,另外链表也有快慢指针技巧。下一篇算法文章讲双指针之左右指针。

微信扫描下方二维码,或搜索“xicheng”,关注公众号后回复【笔记】,有我准备的15万字Java面试笔记。

  感谢各位人才的点赞、收藏和评论,干货文章持续更新中,下篇文章再见!

分类:

后端

标签:

后端

作者介绍

xicheng
V1