Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/283.html
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?
Algorithm
To do in-place replacement method, you need to use two pointers, one of which keeps sweeping backwards to find a non-zero position, and then swap positions with the previous pointer.
Code
-
public class Move_Zeroes { // time: O(N) // space: O(N) class Solution_swap { public void moveZeroes(int[] nums) { if (nums == null || nums.length == 0) { return; } int lastNonZeroAt = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] != 0) { int tmp = nums[lastNonZeroAt]; nums[lastNonZeroAt] = nums[i]; nums[i] = tmp; lastNonZeroAt++; } } } } class Solution { public void moveZeroes(int[] nums) { if (nums == null || nums.length == 0) { return; } int actualP = 0; int scanP = 0; while (scanP < nums.length) { if (nums[scanP] != 0) { nums[actualP++] = nums[scanP++]; } else { scanP++; } } while (actualP < nums.length) { nums[actualP++] = 0; } } } } ############ class Solution { public void moveZeroes(int[] nums) { int left = 0, n = nums.length; for (int right = 0; right < n; ++right) { if (nums[right] != 0) { int t = nums[left]; nums[left] = nums[right]; nums[right] = t; ++left; } } } }
-
class Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ left, n = 0, len(nums) for right in range(n): if nums[right] != 0: nums[left], nums[right] = nums[right], nums[left] left += 1 ############ class Solution(object): def moveZeroes(self, nums): """ :type nums: List[int] :rtype: void Do not return anything, modify nums in-place instead. """ i = j = 0 for i in range(0, len(nums)): if nums[i] != 0: nums[j], nums[i] = nums[i], nums[j] j += 1
-
class Solution { public: void moveZeroes(vector<int>& nums) { int left = 0, n = nums.size(); for (int right = 0; right < n; ++right) { if (nums[right] != 0) { swap(nums[left], nums[right]); ++left; } } } };
-
func moveZeroes(nums []int) { n := len(nums) left := 0 for right := 0; right < n; right++ { if nums[right] != 0 { nums[left], nums[right] = nums[right], nums[left] left++ } } }
-
/** Do not return anything, modify nums in-place instead. */ function moveZeroes(nums: number[]): void { const n = nums.length; let i = 0; for (let j = 0; j < n; j++) { if (nums[j]) { if (j > i) { [nums[i], nums[j]] = [nums[j], 0]; } i++; } } }
-
/** * @param {number[]} nums * @return {void} Do not return anything, modify nums in-place instead. */ var moveZeroes = function (nums) { let left = 0, n = nums.length; for (let right = 0; right < n; ++right) { if (nums[right]) { [nums[left], nums[right]] = [nums[right], nums[left]]; ++left; } } };
-
impl Solution { pub fn move_zeroes(nums: &mut Vec<i32>) { let mut i = 0; for j in 0..nums.len() { if nums[j] != 0 { if j > i { nums[i] = nums[j]; nums[j] = 0; } i += 1; } } } }