【算法】双指针(一)-移动零

目录

一、题目介绍

二、双指针原理

1.当前维护指针

1.1维护方向

(1)条件边界

三、三指针原理

应用

1.快速排序

2.快速选择找元素

2.1找第k大元素

2.2找等于k元素

四、提交代码

一、题目介绍

283. 移动零 - 力扣（LeetCode）

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]

示例 2:

输入: nums = [0] 输出: [0]

提示:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

二、双指针原理

扩容遍历指针、当前维护指针从小维护到大1.当前维护指针1.1维护方向(1)条件边界

根据条件判搬新值 维护一个条件边界

一个动作区间 蓄意的始到末 截出后 开始重复

三、三指针原理

再多一个指针 维护 另一侧来的是非判断两性质块，中间第三块 就是 两剩性质的第三块中间第三块只能分好两剩的性质

75. 颜色分类 - 力扣（LeetCode）

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2]

示例 2：输入：nums = [2,0,1] 输出：[0,1,2]

提示：n == nums.length1 <= n <= 300nums[i] 为 0、1 或 2应用

能实现 排块的基准排序：

左块性质<基准元素，中间第三块性质=基准元素，右块性质>基准元素

无序的左小块  排好的块等元素  无序的右大块1.快速排序

排好 块等元素 —> 快速排序

912. 排序数组 - 力扣（LeetCode）

排好 块等元素 —> 快速排序

给你一个整数数组 nums，请你将该数组升序排列。

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

示例 1：输入：nums = [5,2,3,1] 输出：[1,2,3,5] 解释：数组排序后，某些数字的位置没有改变（例如，2 和 3），而其他数字的位置发生了改变（例如，1 和 5）。

示例 2：输入：nums = [5,1,1,2,0,0] 输出：[0,0,1,1,2,5] 解释：请注意，nums 的值不一定唯一。

提示：1 <= nums.length <= 5 * 104-5 * 104 <= nums[i] <= 5 * 1042.快速选择找元素

排好 无序左小块、块等元素、无序右大块 —> 快速选择找元素全排好下 去找 至少有排序的N*logN只排 三块式基准 下 去找 N2.1找第k大元素

215. 数组中的第K个最大元素 - 力扣（LeetCode）

 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:输入: [3,2,1,5,6,4], k = 2 输出: 5

示例 2:输入: [3,2,3,1,2,4,5,5,6], k = 4 输出: 4

提示：1 <= k <= nums.length <= 105-104 <= nums[i] <= 1042.2找前k小元素

LCR 159. 库存管理 III - 力扣（LeetCode）

仓库管理员以数组 stock 形式记录商品库存表，其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量，返回 顺序不限。

示例 1：输入：stock = [2,5,7,4], cnt = 1 输出：[2]

示例 2：输入：stock = [0,2,3,6], cnt = 2 输出：[0,2] 或 [2,0]

提示：0 <= cnt <= stock.length <= 10000
0 <= stock[i] <= 10000

四、提交代码

public void moveZeroes(int[] nums) { int cur = 0; int dest = -1; // 维护 当前最后一个非0的 边界 while(cur < nums.length) { if(nums[cur] != 0) { int tmp; tmp = nums[++dest];//除最开始时外，就是0的 nums[dest] = nums[cur]; nums[cur] = tmp; // 左边搬过来的 cur已经扫描过的，不用再扫描++ } cur++; } }