Arrays
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.
Constraints:
1 <= nums.length <= 10**4
-2**31 <= nums[i] <= 23**1 - 1
Example 1:
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
Example 2:
Input: nums = [0]
Output: [0]
Two pointers are a good approach. A left pointer saves the position to be updated with non-zero value. A right pointer goes one by one. When the current value at the right is not zero, swap the values on the left and right positions. Then, increment the left.
class MoveZeroes {
public:
void moveZeroes(vector<int>& nums) {
for (int i = 0, j = 0; i < nums.size(); ++i) {
if (nums[i] != 0) {
swap(nums[j++], nums[i]);
}
}
}
};
class MoveZeroes {
public void moveZeroes(int[] nums) {
int tmp;
for (int i = 0, j = 0; i < nums.length; ++i) {
if (nums[i] != 0) {
tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
j++;
}
}
}
}
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var moveZeroes = function(nums) {
for (let i = 0, j = 0; i < nums.length; ++i) {
if (nums[i] != 0) {
[nums[i], nums[j]] = [nums[j], nums[i]];
j++;
}
}
};
class MoveZeroes:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
j = 0
for i in range(len(nums)):
if nums[i] != 0:
nums[j], nums[i] = nums[i], nums[j]
j += 1
# @param {Integer[]} nums
# @return {Void} Do not return anything, modify nums in-place instead.
def move_zeroes(nums)
j = 0
0.upto(nums.size - 1) do |i|
if nums[i] != 0
nums[i], nums[j] = nums[j], nums[i]
j += 1
end
end
end
O(n)
O(1)