讨论/《数组类算法》 - 移动零/
《数组类算法》 - 移动零
共 35 个回复

//跳出传统思维,先把不是零的元素都重新从头安排,剩下的都填零就行了。```
代码块

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        
        int k=0;
        for(int x:nums)
            if(x)
                nums[k++]=x;
        for(int i=k;i<nums.size();++i)
            nums[i]=0;    
    }
};
41

java 0ms 代码

class Solution {
    public void moveZeroes(int[] nums) {
        int zeronums = 0;
        int i = 0;
        for(i = 0; i < nums.length; i++) {
            if(nums[i] == 0) {
                zeronums++;
            } 
            else if(zeronums != 0) {
                nums[i - zeronums] = nums[i];
                nums[i] = 0;
            }
        }
    }
}
14

c++

解法一 冒泡思想

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        // 冒泡 从后给前面找 找到 0 一直交换到最后不是0的地方
        for(int i = n - 1; i >= 0; i--)  
            if(nums[i] == 0)
                for(int j = i; j < n - 1; j++)
                    if(nums[j + 1] != 0)
                        swap(nums[j], nums[j + 1]);
            
    }
};

解法二 双指针
k 维护新的数组,指向最后一个数
另一个指针来遍历原数组
最后剩下的地方置0

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        int k = 0;
        for(auto x :nums)
            if(x) nums[k ++] = x;

        while(k < n) nums[k ++] = 0;

    }
};
8


1,把非0的往前挪

把非0的往前挪,挪完之后,后面的就都是0了,然后在用0覆盖后面的。这种是最容易理解也是最容易想到的,代码比较简单,这里就以示例为例画个图来看下
image.png
image.png

代码如下

    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0)
            return;
        int index = 0;
        //一次遍历,把非零的都往前挪
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0)
                nums[index++] = nums[i];
        }
        //后面的都是0,
        while (index < nums.length) {
            nums[index++] = 0;
        }
    }

看下运行结果
image.png


2,参照双指针解决

这里可以参照双指针的思路解决,指针j是一直往后移动的,如果指向的值不等于0才对他进行操作。而i统计的是前面0的个数,我们可以把j-i看做另一个指针,它是指向前面第一个0的位置,然后我们让j指向的值和j-i指向的值交换

    public void moveZeroes(int[] nums) {
        int i = 0;//统计前面0的个数
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] == 0) {//如果当前数字是0就不操作
                i++;
            } else if (i != 0) {
                //否则,把当前数字放到最前面那个0的位置,然后再把
                //当前位置设为0
                nums[j - i] = nums[j];
                nums[j] = 0;
            }
        }
    }

看一下运行结果
image.png



如果觉得绕,还可以换种写法

    public void moveZeroes(int[] nums) {
        int i = 0;
        for (int j = 0; j < nums.length; j++) {
            //只要不为0就往前挪
            if (nums[j] != 0) {
                //i指向的值和j指向的值交换
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;

                i++;
            }
        }
    }

看下运行结果
image.png


上面的解法都不难,如果还理解不了,我给你讲个故事吧。有两个人A和B,其中A有特异功能,水路,陆路他都能走,而B只能走陆路,不能走水路。题中数组为0的我们把它看做是水路,不为0的我们可以把它看做是陆路,A和B同时出发,走的时候,无论是水路还是陆路,A都会往前走一步。而B只能遇到陆路才能走,遇到水路就掉到水里,走不动了,这个时候A可以继续走水路,当A往前走找到陆路的时候就把陆路踢到B的面前,然后B就可以继续走了。


这里就以示例 [0,1,0,3,12]为例,来看下AB的对话。

初始状态:咱哥俩一起走

第1步

  • B:兄弟救我,我掉进水里了。
  • A:兄弟别急,我也在水里,我到前面找块陆地给你

第1步之后数组的值是[0,1,0,3,12]


第2步

  • A:兄弟,我找到陆地1了,踢给你,你接着(把1踢给B)
  • B:好嘞

第2步之后数组的值是[1,0,0,3,12]


第3步

  • B:兄弟,我又掉进水里了
  • A:别急,我也在水了,我在到前面看看有没有陆地,找块给你

第3步之后数组的值是[1,0,0,3,12]


第4步

  • A:兄弟,我找到陆地3了,踢给你,你接着(把3踢给B)
  • B:好嘞

第4步之后数组的值是[1,3,0,0,12]


第5步

  • B:兄弟,我又掉水里了,快来救救我
  • A:我现在在陆地12上面,我把它踢给你吧
  • B:好嘞,谢了,兄弟

第5步之后数组的值是[1,3,12,0,0]


我把部分算法题整理成了PDF文档,截止目前总共有900多页,大家可以下载阅读
链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

如果觉得有用就给个赞吧,还可以关注我的LeetCode主页查看更多的详细题解

6

python

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
 
        for i in nums:
            if  i ==0:
                nums.remove(i)
                nums.append(0)
5
var moveZeroes = function(nums) {
    let index = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i]) {
            nums[index++]=nums[i];
        }
    }
    for (let i = index; i < nums.length; i++) {
        nums[i] = 0;
    }
};

这道题考查了数组这类数据结构。函数内执行了两次for循环,第一个for循环将非零的元素向前移动,第二个for循环是根据index标记零下标的位置开始进行填充零的操作。假设第一个for循环的时间复杂度是n,第二个for的时间复杂度是m,因此,时间复杂度为O(n+m);
解法:双下标定位

2

可以的

2
class Solution {
    public void moveZeroes(int[] nums) {
        //对0计数而无需移动0
        int count=0,len=nums.length;
        for(int i=0;i<len;i++){
            if(nums[i]==0) count++;
            else{
                nums[i-count]=nums[i];
            }
        }
        for(int i=0;i<count;i++){
            nums[len-count+i]=0;
        }

    }
}
1

C 实现

void moveZeroes(int* nums, int numsSize){
    int left = 0;
    for (int right = 0; right < numsSize; right++) {
        if (nums[right] != 0) {
            int temp = nums[left];
            nums[left++] = nums[right];
            nums[right] = temp;
        }
    }
}
1

奈斯

1