1.移动零
题目链接:移动 0_牛客题霸_牛客网 (nowcoder.com)
算法原理:
像这样子的将一整块数组划分很多部分可以称为数组划分,常用的解法可以是双指针。
说是双指针,但操作的对象是数组,因此下标就是指针。
双指针的精华就是通过俩个指针将数组划分成三个部分:
那我们让其这个规则贯彻就完成了
想要保证上述划分的区域不变的话,那就可以这样做:
先让left指向 -1 ,right进行扫描整个数组。
right遇到0继续++,遇到非0的话,然后swap(nums[left+1] ,nums[right]left++, right++
public int[] moveZeroes (int[] nums) {
// write code here
int left = -1;
int right = 0;
for(int i = 0;i < nums.length;i++){
if(nums[right] == 0){
right++;
}else{
swap(left+1,right,nums);
left++;
right++;
}
}
return nums;
}
public void swap(int left,int right,int[] nums){
int num = nums[left];
nums[left] = nums[right];
nums[right] = num;
}
2.复写零
算法原理:
看到这个题第一个想到的是:创建一个新的数组,遍历原数组然后普通数字直接复制到新数组上,0就复制俩次呗。
但是有没有可以实现在这数组上直接进行操作呢?
我们先从前往后试着模拟一下:
我们发现left会往前越过right,并且覆盖掉了 2这显然不可以的,那我们就试着从后往前遍历。
那如果从后往前遍历的话,right指标肯定要先指向原数组最后的一个位置就比如上述的数据,right应该指向 val数据是 4 。left指向的是最后的元素。然后往前进行遍历,就不会出现覆盖的情况了。
那就还有个问题,就是如何找到原数组最后出现的数呢?也可以用双指针从前往后,找到right最后的位置,然后left不需要进行换数据啥的,主要就是为了找到位置。
具体的步骤如下:
文章来源:https://www.toymoban.com/news/detail-693882.html
文章来源地址https://www.toymoban.com/news/detail-693882.html
public void duplicateZeros(int[] arr) {
//1.先找到原数组最后出现的位置 right就是目标位置
int n = arr.length;
int top = 0;
int i = -1;
while(top < n){
i++;
if(arr[i] != 0){
top++;
}else{
top += 2;
}
}
//边界问题
int j = n - 1;
if(top == n + 1){
arr[j] = 0;
j--;
i--;
}
//从后往前遍历
while(j >= 0){
arr[j] = arr[i];
j--;
if(arr[i] == 0){
arr[j] = arr[i];
j--;
}
i--;
}
}
到了这里,关于算法专栏——双指针的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!