Description
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.
Example 1:
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
Example 2:
Input: nums = [0]
Output: [0]
Constraints:
1 <= nums.length <= 104-231 <= nums[i] <= 231 - 1
Follow up: Could you minimize the total number of operations done?
Solutions
Solution 1: Two Pointers
We use a pointer k to record the current position to insert, initially k = 0.
Then we iterate through the array nums, and each time we encounter a non-zero number, we swap it with nums[k] and increment k by 1.
This way, we can ensure that the first k elements of nums are non-zero, and their relative order is the same as in the original array.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
PythonJavaC++GoTypeScriptRustJavaScriptC
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
k = 0
for i, x in enumerate(nums):
if x:
nums[k], nums[i] = nums[i], nums[k]
k += 1(code-box)
class Solution {
public void moveZeroes(int[] nums) {
int k = 0, n = nums.length;
for (int i = 0; i < n; ++i) {
if (nums[i] != 0) {
int t = nums[i];
nums[i] = nums[k];
nums[k++] = t;
}
}
}
}(code-box)
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int k = 0, n = nums.size();
for (int i = 0; i < n; ++i) {
if (nums[i]) {
swap(nums[i], nums[k++]);
}
}
}
};(code-box)
func moveZeroes(nums []int) {
k := 0
for i, x := range nums {
if x != 0 {
nums[i], nums[k] = nums[k], nums[i]
k++
}
}
}(code-box)
/**
Do not return anything, modify nums in-place instead.
*/
function moveZeroes(nums: number[]): void {
let k = 0;
for (let i = 0; i < nums.length; ++i) {
if (nums[i]) {
[nums[i], nums[k]] = [nums[k], nums[i]];
++k;
}
}
}(code-box)
impl Solution {
pub fn move_zeroes(nums: &mut Vec<i32>) {
let mut k = 0;
let n = nums.len();
for i in 0..n {
if nums[i] != 0 {
nums.swap(i, k);
k += 1;
}
}
}
}(code-box)
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var moveZeroes = function (nums) {
let k = 0;
for (let i = 0; i < nums.length; ++i) {
if (nums[i]) {
[nums[i], nums[k]] = [nums[k], nums[i]];
++k;
}
}
};(code-box)
void moveZeroes(int* nums, int numsSize) {
int k = 0;
for (int i = 0; i < numsSize; ++i) {
if (nums[i] != 0) {
int t = nums[i];
nums[i] = nums[k];
nums[k++] = t;
}
}
}(code-box)
