讨论/《排序算法全解析》 - 283. 移动零/
《排序算法全解析》 - 283. 移动零
共 26 个回复

HR:你冒个泡试试?

8
class Solution {
    public void moveZeroes(int[] nums) {
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                if (i > j) {
                    nums[j] = nums[i];
                    nums[i] = 0;
                }
                j++;
            }
        }
    }
}
5

小编:我就是要冒泡

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i < n - 1; i ++){
            for(int j = 0; j < n - 1 - i; j ++){
                if(nums[j] == 0)
                    swap(nums[j], nums[j + 1]);
            }
        }
    }
};
3

O(n)的时间复杂度,O(1)的空间复杂度

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int len=nums.size();
        int zeroNum=0;
        for(int i=0;i<len;i++){
            if(nums[i]==0)zeroNum++;
            else{
                nums[i-zeroNum]=nums[i];
            }
        }
        for(int j=len-1;j>len-1-zeroNum;j--){
            nums[j]=0;
        }
    }
};
2
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        std::fill(std::remove(nums.begin(), nums.end(), 0), nums.end(), 0);
    }
};
1

啊这,这里用冒泡hr直接叫回去等通知了叭

2

再来个没优化的稳定性的:

class Solution {
    public void moveZeroes(int[] nums) {
         int i = 0, j = 0;
        //找不等于0的放在第一位
        while (j < nums.length) {
            if (nums[j] != 0) {
                int tmp = nums[i];
                nums[i++] = nums[j];
                nums[j] = tmp;
            }
            j++;
        }
    }
}

相对位置发生了变化,但是快排会用到这个思想

class Solution {
    public void moveZeroes(int[] nums) {
         int i = 0, j = nums.length - 1;

        while (j > i) {//j<i(最后的值有0发生了交换),i==j(说明前面都不为0,后面都为0)
            if (nums[i] == 0) {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j--] = tmp;
            } else {
                i++;
            }
        }
    }
}

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

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        if(nums.size()==0){
            return;
        }
        for(int i=0;i<nums.size();i++){
            for(int j=0;j<nums.size()-1-i;j++){
                if(nums[j]==0){
                    nums[j]=nums[j+1]^nums[j];
                    nums[j+1]=nums[j]^nums[j+1];
                    nums[j]=nums[j]^nums[j+1];
                }
            }
        }
    }
};