企业网站 更新 seo,注册邮箱,天津做网站认准津坤科技,wordpress 取消做这题目引用
这里以 1、LeetCode704.二分查找 2、LeetCode27.移除元素 3、LeetCode977.有序数组的平方 这三道题举例来说明数组中双指针的妙用。
1、二分查找
给定一个 n 个元素有序的#xff08;升序#xff09;整型数组 nums 和一个目标值 target #xff0c;写一个函数搜…题目引用
这里以 1、LeetCode704.二分查找 2、LeetCode27.移除元素 3、LeetCode977.有序数组的平方 这三道题举例来说明数组中双指针的妙用。
1、二分查找
给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果目标值存在返回下标否则返回 -1。 首先我们来理解一下题意 我们需要在一段连续递增的数组当中找到 target 元素并在函数结尾返回它。 暴力的解法是直接把数组遍历一遍一一比对找到后返回。当然时间复杂度会是 O(N) 级别的。 那么有没有更简便的写法呢 当然有那就是我们今天要见识到的 双指针算法。 首先我们初始化两个指针一个指向数组的头left另一个指向数组的尾right。并且维护一个 mid 指针使其始终处于 [left,right] 范围内比较数组 mid 位置与target 的数值大小。如果 mid 位置的数值比target大那么将right移动到mid位置再次更新mid位置。如果 mid 位置的数值比target小那么将left移动到mid位置再次更新mid位置。如此循环直到找到 target 值的位置或者 leftright 循环结束。 注意由于区间的个人喜好不同一般有左闭右开写法和左闭右闭两种写法。 左闭右开写法
int search(vectorint nums, int target) {int left0,rightnums.size();while(leftright){int mid(leftright)1;if(targetnums[mid]){leftmid1;}else if(targetnums[mid]){rightmid;}else{return mid;}}return -1;}左闭右闭写法
int search(vectorint nums, int target) {int left0,rightnums.size()-1;while(leftright){int mid(leftright)1;if(targetnums[mid]){leftmid1;}else if(targetnums[mid]){rightmid-1;}else{return mid;}}return -1;}那么这题就被完美地解决了~
2、移除元素
给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k要通过此题您需要执行以下操作
更改 nums 数组使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。 返回 k。
我们来理解一下题意 给了我们一个存储着随机元素且随机长度的数组让我们来移除 val 的元素这道题当然可以遍历一遍数组将数组中 val 的元素全部覆盖掉但是这样是很容易丢失数据位置进而引发结果错误的。那么应该怎么写才能快速而优雅地AC它呢当然还是双指针。 我们定义两个指针一个快指针fast一个慢指针slow。我们让fast指针先走边走边判断数组中的元素是否 val 。如果等于我们继续往下走(是不是很奇怪别急慢慢看)如果 !val 我们让fast位置的值和slow位置的值交换并且 slow。当fast走到数组末尾的时候返回slow。 为什么 为什么slow位置就能代表 !val 的所有元素的数目呢 我来画个图给大家看看 所以返回slow就会是被移除后的元素数量。 附上代码
int removeElement(vectorint nums, int val) {int slow0;for(int fast0;fastnums.size();fast){if(nums[fast]!val) nums[slow]nums[fast];}return slow;}这题也就完美的完成啦~
3、有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums返回 每个数字的平方 组成的新数组要求也按 非递减顺序 排序。
这题我们也分析一下下~ 首先用暴力算完再排序也是可以的~但我们是手艺人不能题题都暴力。 这题也是给我们一个非递减数组也就是要么增要么等。那么还是使用双指针来解吧。定义一个头指针i尾指针j遍历数组比较 nums[i] , nums[j] 平方后的大小 i 位置的平方比较大就交换反之则将 平方后的数 放回数组对应位置继续循环。 直接上代码
vectorint sortedSquares(vectorint nums) {int n nums.size();vectorint ans(n);int i 0, j n - 1;for (int p n - 1; p 0; p--) {int x nums[i], y nums[j];if (-x y) {ans[p] x * x;i;} else {ans[p] y * y;j--;}}return ans;}总结
双指针算法既简便又能快速解决问题如果我们遇到数组相关的问题可以积极考虑它。
