做户外商城网站,成都软件开发工资一般多少,建筑工程类人才招聘,一键生成vi设计数组双指针专题 1.同向双指针1.1例题26.删除有序数组中的重复项27.移除元素80.删除有序数组中的重复项 Ⅱ 2.相向双指针2.1例题11.盛最多水的容器42.接雨水581.最短无序连续子数组 双指针在算法题中很常见#xff0c;下面总结双指针在数组中的一些应用#xff0c;主要分为两类… 数组双指针专题 1.同向双指针1.1例题26.删除有序数组中的重复项27.移除元素80.删除有序数组中的重复项 Ⅱ 2.相向双指针2.1例题11.盛最多水的容器42.接雨水581.最短无序连续子数组 双指针在算法题中很常见下面总结双指针在数组中的一些应用主要分为两类
1.同向双指针
题目中有原地、不适用额外空间等关键词一般解决方法是定义两个快慢指针 快指针用来遍历数组并进行一些规则匹配 慢指针用来表示结果数组即当前符合条件的数组
最后一般是返回慢指针的下标需要注意的是有时候不能只返回慢指针的下标可能需要1需要根据实际情况分析。
1.1例题
26.删除有序数组中的重复项
思路 本题设置一个辅助下标指针idx指向数组的第一个元素然后往后遍历数组如果遇到了相同的元素就跳过遇到不同的元素则加入到辅助下标的后一个元素依次类推直到遍历数组结束最后返回idx1即为所求的长度。详细的视频讲解点击视频讲解-删除有序数组中的重复项。 时间复杂度 时间复杂度为O(n)只进行了一次数组的遍历。 代码实现
class Solution {public int removeDuplicates(int[] nums) {if(nums.length 2) return nums.length;int idx 0;for(int i 1;i nums.length;i){if(nums[i] ! nums[idx]){idx idx 1;nums[idx] nums[i];}}return idx 1;}
}27.移除元素
思路 本题的思路和第26题一样需要一个辅助下标idx遍历整个数组当遇到数组元素不等于val时则将其加入到删除后的数组中同时辅助下标后移遍历结束后返回辅助下标idx的值即可详细的视频讲解点击视频讲解-移除元素。 时间复杂度 时间复杂度为O(n)n为数组的长度。 代码实现
class Solution {public int removeElement(int[] nums, int val) {int idx 0;for(int i 0;i nums.length;i){if(nums[i] ! val){nums[idx] nums[i];idx idx 1;}}return idx;}
}80.删除有序数组中的重复项 Ⅱ
思路 本题采用双指针来求解解法和26.删除有序数组中的重复项类似但是由于本题中每个元素可以出现两次所以将idx设置为1设置前两个位置为结果数组第二个指针从索引为2开始比较当前元素和结果数组中的倒数第二个元素的值是否相等即nums[idx - 1]注意这里不要使用nums[--idx]因为这样会改变idx的值导致索引不正确如果相等则i继续向后遍历如果不相等则加入到结果数组中这里可以这样做的原因是nums是有序数组如果是无序数组则不能这么做下面是一个模拟的例子 视频讲解点击视频讲解-删除有序数组中的重复项 Ⅱ 时间复杂度 时间复杂度为O(n)其中n为数组的长度。 代码实现
class Solution {public int removeDuplicates(int[] nums) {if(nums.length 2) return nums.length;int idx 1;for(int i 2;i nums.length ; i){if(nums[i] ! nums[idx - 1]){nums[idx] nums[i];}}return idx 1;}
}2.相向双指针
双指针 一般是一个在开头一个在结尾两者相向处理问题一般用来确定某个符合条件的子数组需要维护左右边界。
2.1例题
11.盛最多水的容器
思路 本题采用双指针来求解由于盛水的体积为宽✖高因此可以定义首尾两个指针枚举出不同高度的体积并取最大值在移动指针的过程中应该移动高度较小的指针因为盛水的高度是由短板来决的如图不同的颜色表示每次移动指针后得到的体积。视频讲解点击视频讲解-盛最多水的容器。
时间复杂度 时间复杂度为O(n)空间复杂度O(1)。 代码实现
class Solution {public int maxArea(int[] height) {int ans 0;int l 0;int r height.length - 1;while(l r){ans Math.max(ans,Math.min(height[l],height[r]) * (r-l));if(height[l] height[r]) l;else r--;}return ans;}
}42.接雨水
思路 本题采用双指针来求解类似于11.盛水最多的容器盛水的多少取决于左右柱子里较低的一个。通过维护左边和右边的最大高度来计算整个数组中的装水容量定义两个变量lmax和rmax初始值都为0用于记录当前位置左边和右边的最大高度不断更新左右两边的最大高度来计算每个位置的水位然后将各个位置的水位差累加起来得到总的装水容量下面是一个模拟的例子 视频讲解点击视频讲解-接雨水。 时间复杂度 这段代码的时间复杂度是O(n)其中n是height数组的长度。由于只使用了一个while循环来遍历height没有嵌套的循环因此时间复杂度是线性的。 代码实现
class Solution {public int trap(int[] height) {int l 0;int r height.length - 1;int lmax 0;int rmax 0;int ans 0;while(l r){lmax Math.max(lmax,height[l]);rmax Math.max(rmax,height[r]);if(lmax rmax){ans lmax - height[l];l;} else{ans rmax - height[r];r--;}}return ans;}
}581.最短无序连续子数组
思路 本题采用双指针解决分别从数组的两端进行遍历确定结果数组的左右边界。确定左边界的条件如果当前元素小于左边界处的最大值则更新右边界否则更新左边界的最大值左边界的右边不应该出现比左边界小的值确定右边界的条件是如果当前元素大于右边界处的最小值则更新左边界否则更新右边界的最小值右边界的左边不应该出现比右边界大的值得到左右边界后返回子数组的长度即可。 时间复杂度 时间复杂度为O(n)n为数组长度。 代码实现
class Solution {public int findUnsortedSubarray(int[] nums) {//初始化工作//start、end分别是从前向后和从后向前遍历数组的两个指针//需要注意的是end不是从len - 1开始初始值应该为-1这是为了处理数组本来就是有序数组的情况//lmax、rmin分别是遍历过程中维护的左边界的最大值和右边界的最小值int len nums.length;int start 0;int end -1;int lmax nums[0];int rmin nums[len - 1]; for(int i 0;i len ; i){//确定左边界if(nums[i] lmax){end i;} else {lmax nums[i];}//确定右边界if(nums[len - i - 1] rmin){start len - i -1;} else {rmin nums[len - i -1];}}return end - start 1;}
}参考资料双指针-数组
