1.双指针法
文章目录
- 1.双指针法
- 1.1什么是双指针法?
- 1.2解题思路
- 1.3扩展
1.1什么是双指针法?
双指针算法是一种在数组或序列上操作的技巧,实际上是对暴力枚举算法的一种优化,通常涉及到两个索引(或指针)从两端或从某个特定起点开始向中间靠拢,以解决特定问题。这种算法在处理数组中的元素对、查找、排序和去除重复元素等问题上特别有效。
- 初始化:设定两个指针,它们可以同时从序列的两端开始,也可以从同一端以不同速度移动。
- 移动规则:根据问题需求定义指针如何移动。比如,在排序数组中查找一对数之和,一个指针可以从左向右移动,另一个从右向左移动,直到两者相遇。
- 终止条件:当指针相遇、错过彼此或是达到某种特定条件时,算法结束。
典型应用场景:
-
查找问题
- 在排序数组中查找目标对:给定一个排序数组和一个目标值,找到两个数,使它们的和为目标值。如 LeetCode 的 “Two Sum II - Input array is sorted” 问题。
-
删除问题
- 移除数组中的重复元素:例如,给定一个排序数组,原地删除重复出现的元素,使得每个元素最多出现两次。双指针一个用来遍历,另一个用来记录新的非重复元素的位置。
-
排序与翻转
- 反转数组:可以使用双指针快速地原地反转数组的一部分或全部。两个指针一前一后交换元素直至相遇。
-
滑动窗口
- 最大/最小滑动窗口:维护一个大小固定的窗口,在数组上滑动以找到窗口内的最大值或最小值,或某些统计量,如窗口内的最大和。
1.2解题思路
题目原文:
给你一个按 非递减顺序 排序的整数数组 nums
,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
示例 1:
输入:nums = [-4,-1,0,3,10]
输出:[0,1,9,16,100]
解释:平方后,数组变为 [16,1,0,9,100]
排序后,数组变为 [0,1,9,16,100]
示例 2:
输入:nums = [-7,-3,2,3,11]
输出:[4,9,9,49,121]
思路:
对于这个问题,双指针算法可以非常高效地解决。由于原始数组是非递减排序的,我们可以通过双指针从数组两端开始向中间遍历,比较两个指针所指向元素的平方值,将较大的平方值先放入结果数组中。这样可以确保结果数组始终是按非递减顺序排列的。
- 初始化两个指针,
left
指向数组的起始位置,right
指向数组的末尾位置。 - 初始化一个空数组或列表来存放结果。
- 当
left <= right
时,执行以下步骤:- 计算
left
和right
指针所指向元素的平方值。 - 比较这两个平方值,将较大的那个平方值添加到结果数组的前端。
- 移动指向较小原数值的指针。如果平方值相等,可以任选一个指针移动。
- 计算
- 当
left > right
时,所有元素都已经处理完毕,返回结果数组。
通过这种方法,我们可以在一次遍历中完成所有计算和排序工作,时间复杂度为O(n),空间复杂度也为O(n),其中n为数组的长度。
class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {vector<int>result(nums.size(),0);int left = 0;int right = nums.size() - 1;int k = nums.size() - 1;while(left <= right){if(nums[left]*nums[left] < nums[right]*nums[right]){result[k--] = nums[right]*nums[right];right--;}else{result[k--] = nums[left]*nums[left];left++;}}return result;}
};
1.3扩展
题目原文:
给你两个按 非递减顺序 排列的整数数组 nums1
和 nums2
,另有两个整数 m
和 n
,分别表示 nums1
和 nums2
中的元素数目。
请你 合并 nums2
到 nums1
中,使合并后的数组同样按 非递减顺序 排列。
**注意:**最终,合并后数组不应由函数返回,而是存储在数组 nums1
中。为了应对这种情况,nums1
的初始长度为 m + n
,其中前 m
个元素表示应合并的元素,后 n
个元素为 0
,应忽略。nums2
的长度为 n
。
示例 1:
输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出:[1,2,2,3,5,6]
解释:需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ,其中斜体加粗标注的为 nums1 中的元素。
示例 2:
输入:nums1 = [1], m = 1, nums2 = [], n = 0
输出:[1]
解释:需要合并 [1] 和 [] 。
合并结果是 [1] 。
示例 3:
输入:nums1 = [0], m = 0, nums2 = [1], n = 1
输出:[1]
解释:需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意,因为 m = 0 ,所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
思路:
双指针解题思路在这种合并有序数组的问题中非常有效。这里的关键是利用两个数组已经是非递减顺序的特点,通过两个指针分别从两个数组的末尾开始比较,并将较大的数逆序填入nums1的末尾
解题步骤:
-
初始化两个指针
i
和j
,分别指向nums1
和nums2
的末尾,即i = m - 1
和j = n - 1
。同时,设置另一个指针k
指向nums1
数组的最后一个有效位置,即k = m + n - 1
。 -
当
i >= 0
且j >= 0
时,进行以下操作:- 比较
nums1[i]
和nums2[j]
的值。 - 将较大的数赋值给
nums1[k]
,然后对应的指针向前移动一位。如果nums1[i]
大,则i--
;如果nums2[j]
大或相等,则j--
。 k--
,因为每次操作都是在数组的末尾进行的。
- 比较
-
如果
j >= 0
,说明nums2
中还有剩余元素,直接将剩余的nums2[j]
逐个复制到nums1
的前面,因为nums2
的元素在nums1
的末尾已经被正确地放置了。
class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {vector<int> arr(m + n, 0); // 创建一个足够大的临时数组int k = m + n - 1; // 初始化k为新数组的最后一个位置索引m--; // nums1的有效元素索引需要减1,因为m是原始长度n--; // nums2的同理// 注意循环条件应该是 k >= 0,因为我们要从末尾开始填充while (k >= 0) {if (n < 0) { // 如果nums2已经全部处理完了arr[k] = nums1[m];m--;} else if (m < 0) { // 如果nums1已经全部处理完了arr[k] = nums2[n];n--;} else if (nums1[m] > nums2[n]) { // 比较条件arr[k] = nums1[m];m--;} else {arr[k] = nums2[n];n--;}k--; // 移动到下一个待填充的位置}// 最后把合并的结果复制回nums1nums1.swap(arr);}
};