LeetCode初级算法——移动零

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

示例:

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

说明:

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

解题思路:

解法一:

由于不能使用额外数组,所以一开始想到的就是移动数组中的元素,用一个标志位index记录移动后0的位置,逆序遍历数组,当位置i的元素为0时,将index-1到i之间的数向左移动一位,再将index处的元素置为0,用图来看,就是:

[0, 1, 0, 3, 12]

[0, 1, 3, 12, 0]

[1, 3, 12, 0, 0]

代码如下:


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

执行时间:29ms

每次找到0就要移动数组元素,效率确实挺差的。

解法二:

顺序遍历数组,如果元素为0,再向后遍历数组,当遇到不为0的元素时,将该元素与0交换,整个过程有点类似冒泡排序,逐渐将0冒泡到数组尾部,用图来看,就是:

[0, 1, 0, 3, 12]

[1, 0, 0, 3, 12]

[1, 3, 0, 0, 12]

[1, 3, 12, 0, 0]

代码如下:

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

执行时间:23ms

由于不用每次找到0时都移动数组元素,而只是交换了一下元素位置,所以比起解法一效率稍微高一点。但还是用到了双层循环,到底有没有办法将时间复杂度降低到线性?答案是肯定的。

解法三:

用一个标志位index记录不为0的元素的下标,遍历数组,当元素不为0时,将该元素赋值给index位置,最后再将index到nums.length之间的元素置为0,用图来看,就是:

[0, 1, 0, 3, 12]

[1, 1, 0, 3, 12]

[1, 3, 0, 3, 12]

[1, 3, 12, 3, 12]

[1, 3, 12, 0, 0]

代码如下:

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

执行时间:2ms

线性时间复杂度果真快多了有木有!!!而且代码也超级简洁~突然间不是那么讨厌算法了,继续加油!共勉!

 

 

 

文章已创建 65

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部