讨论/《排序算法全解析》 - 解析/
《排序算法全解析》 - 解析
共 9 个回复

冒泡法做的话太慢了,下面解法也是交换,只不过是通过快慢指针,让非零元素(快指针)跟末尾的0元素(慢指针)交换。时间复杂度只有O(n)。

class Solution {
    public void moveZeroes(int[] nums) {
        int i=0,j=0;
        while(j<nums.length){
            if(nums[j]!=0){
                if(nums[i]==0){
                    nums[i]=nums[j];
                    nums[j]=0;
                }
                i++;
            }
            
            j++;
        }
    }
}
14

同样的代码提交第一次击败17,第二次击败88.
离谱

2
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++;
            }
        }
    }
}
2

可能你击败了自己

哈哈哈,咱俩一样,超过的5%怕不是官方的托

只需要遍历一下,把非0的数赋值到前面,然后设置原来的值为0.

public void moveZeroes(int[] nums) {
        int replaceIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[replaceIndex] = nums[i];
                if (replaceIndex != i) {
                    nums[i] = 0;
                }
                replaceIndex++;
            }
        }
    }

Python大法好!

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        n = nums.count(0)
        for i in range(n):
            nums.remove(0)
        nums.extend([0]*n)

python 使用冒泡排序,是真的慢,我想知道被我超越的百分之5是用什么方法做的,哈哈

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        for i in range(0,n):
            for j in range(0,n-1-i):
                if nums[j] == 0:
                    nums[j+1] = nums[j+1] + nums[j]
                    nums[j] = nums[j+1] - nums[j]
                    nums[j+1] = nums[j+1] - nums[j]
        return nums
class Solution {
 public:
  void moveZeroes(vector<int>& nums) {
    /* 冒泡 */
    // bool swaped = true;
    // int n = nums.size(), last = -1, right = n - 1;
    // while (swaped) {
    //   swaped = false;
    //   for (int i = 0; i < right; i++) {
    //     if (nums[i] == 0) {
    //       swap(nums[i], nums[i + 1]);
    //       swaped = true;
    //       last = i;
    //     }
    //   }
    //   right = last;
    // }
    /* 双指针 */
    int j = 0;
    for (int i = 0; i < nums.size(); i++) {
      if (nums[i] != 0) swap(nums[i], nums[j++]);
    }
  }
};