【算法】双指针(一)-移动零
目录
一、题目介绍
给定一个数组 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++; } }
