LeetCode算法解析之“移动零”问题_leetcode移动零算法题

题目描述：

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:

1. 必须在原数组上操作，不能拷贝额外的数组。
2. 尽量减少操作次数。

解法一：

class Solution {
    public void moveZeroes(int[] nums) {

        int i,j,t;
        for(i=0;i<nums.length;i++){
            for(j=0;j<(nums.length-1)-i;j++){
                if(nums[j]==0){
                    t=nums[j+1];
                    nums[j+1]=nums[j];
                    nums[j]=t;
                }
            }
        }
System.out.println(nums);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

这个方法使用的双重for循环，时间复杂度很高，属于”蛮力“求解

解法二：

class Solution {
	public void moveZeroes(int[] nums) {
		if(nums==null) {
			return;
		}
		//第一次遍历的时候，j指针记录非0的个数，只要是非0的统统都赋给nums[j]
		int j = 0;
		for(int i=0;i<nums.length;++i) {
			if(nums[i]!=0) {
				nums[j++] = nums[i];
			}
		}
		//非0元素统计完了，剩下的都是0了
		//所以第二次遍历把末尾的元素都赋为0即可
		for(int i=j;i<nums.length;++i) {
			nums[i] = 0;
		}
	}
}	

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

解法三：

class Solution {
    public void moveZeroes(int[] nums) {

        int i=0;//找0
        int j=0;//找非0
        while(j<nums.length){
            if(nums[j]!=0){
                int t=nums[j];
                nums[j]=nums[i];
                nums[i]=t;
                i++;
            }
            j++;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

这个解法效率就很高！ 值得推荐。
如题案例，此种解法一共只需要比较三次，就完成了排序！