Leetcode 283:Move Zeros
程序员文章站
2024-02-17 10:19:04
...
问题描述:
Given an integer array nums, move all 0’s to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.
把0都移到数组后面
限制条件:
1 <= nums.length <= 104
-2^31 <= nums[i] <= 2 ^31 - 1
思路:
用一个指针从前面遍历。遇到0就交换到末尾。末尾还有一个指针,永远指向一个非0元素。但这个思路被证实是错的,因为会破坏原序
思路更正:
可以设两个指针(slow,fast)都是从0开始,fast指针用从头到尾作遍历数组的指针。如果fast指向的不是0,就交换slow和fast,完事后两个指针均继续向前走;若fast指向的是0,slow作为定位指针不动,fast继续向前探索。
代码一遍通过:
class Solution {
public void moveZeroes(int[] nums) {
int slow = 0;
int temp;
for (int fast=0; fast<nums.length; fast++){
if (nums[fast]!=0) {
//swap nums[slow] and nums[fast]
temp = nums[fast];
nums[fast] = nums[slow];
nums[slow] = temp;
slow++;
}
}
}
}
时间复杂度: O(n)