【算法day1】数组：双指针算法

标题引用

这里以
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 值的位置大概 left>right 循环结束。
注意：由于区间的个人喜欢不同，一般有左闭右开写法和左闭右闭两种写法。
左闭右开写法：

1. int search(vector<int>& nums, int target) {
2.         int left=0,right=nums.size();
3.         while(left<right){
4.             int mid=(left+right)>>1;
5.             if(target>nums[mid]){
6.                 left=mid+1;
7.             }else if(target<nums[mid]){
8.                 right=mid;
9.             }else{
10.                 return mid;
11.             }
12.         }
13.         return -1;
14.     }

复制代码

左闭右闭写法：

1. int search(vector<int>& nums, int target) {
2.         int left=0,right=nums.size()-1;
3.         while(left<=right){
4.             int mid=(left+right)>>1;
5.             if(target>nums[mid]){
6.                 left=mid+1;
7.             }else if(target<nums[mid]){
8.                 right=mid-1;
9.             }else{
10.                 return mid;
11.             }
12.         }
13.         return -1;
14.     }

复制代码

那么这题就被完善地解决了~
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就会是被移除后的元素数量。
附上代码

1. int removeElement(vector<int>& nums, int val) {
2.         int slow=0;
3.         for(int fast=0;fast<nums.size();fast++){
4.             if(nums[fast]!=val) nums[slow++]=nums[fast];
5.         }
6.         return slow;
7.     }

复制代码

这题也就完善的完成啦~
3、有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
这题我们也分析一下下~
起首用暴力算完再排序也是可以的~但我们是手艺人，不能题题都暴力。
这题也是给我们一个非递减数组，也就是要么增要么等。那么照旧利用双指针来解吧。界说一个头指针i，尾指针j，遍历数组，比力 nums , nums[j] 平方后的大小， i 位置的平方比力大就交换，反之则将 平方后的数 放回数组对应位置继续循环。
直接上代码

1. vector<int> sortedSquares(vector<int>& nums) {
2.        int n = nums.size();
3.        vector<int> ans(n);
4.        int i = 0, j = n - 1;
5.        for (int p = n - 1; p >= 0; p--) {
6.            int x = nums[i], y = nums[j];
7.            if (-x > y) {
8.                ans[p] = x * x;
9.                i++;
10.            } else {
11.                ans[p] = y * y;
12.                j--;
13.            }
14.        }
15.        return ans;
16.    }

复制代码

总结

双指针算法既简便又能快速解决问题，如果我们碰到数组相干的问题可以积极考虑它。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。