This is a leetcode puzzle: You can submit your solutions to this URL: https://leetcode.com/problems/move-zeroes/
Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements. For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].
1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.
O(n^2) solution
The following O(n2) solution has runtime 72ms, which passes 21 test cases on the judge server. The idea is to check each number for the right-to-left directory. If it is zero, then move the next numbers 1 position to the left and move the zero the the right.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | class Solution { public: void moveZeroes(vector<int>& nums) { int len = nums.size(); if (len == 0) return; for (int j = len - 1; j >= 0; j --) { // checking for the tail if (nums[j] == 0) { int i = j; for (; (i < len - 1) && (nums[i + 1] != 0); i ++) { // move 1 number to the left nums[i] = nums[i + 1]; } nums[i] = 0; // move zero to the right } } } }; |
class Solution { public: void moveZeroes(vector<int>& nums) { int len = nums.size(); if (len == 0) return; for (int j = len - 1; j >= 0; j --) { // checking for the tail if (nums[j] == 0) { int i = j; for (; (i < len - 1) && (nums[i + 1] != 0); i ++) { // move 1 number to the left nums[i] = nums[i + 1]; } nums[i] = 0; // move zero to the right } } } };
The idea is simple, and it is a O(n2) algorithm, so it is not optimal.
O(n) solution
We can have 1 pointer (indexing pointer). It points to the current non-zero element to be filled, by scanning from the left to the right only filling non-zero elements gives a O(n) solution.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | class Solution { public: void moveZeroes(vector<int>& nums) { int len = nums.size(); int j = 0; for (int i = 0; i < len; i ++) { if (nums[i] != 0) { nums[j ++] = nums[i]; } } for (; j < len; j ++) { nums[j] = 0; } } }; |
class Solution { public: void moveZeroes(vector<int>& nums) { int len = nums.size(); int j = 0; for (int i = 0; i < len; i ++) { if (nums[i] != 0) { nums[j ++] = nums[i]; } } for (; j < len; j ++) { nums[j] = 0; } } };
However, we would need a second O(n) loop) to fill the zeros to the end of the array.
We can further reduce to only 1 single O(n) loop by swapping the zeros with the non-zeros (making nonzero numbers jumping to the left).
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution { public: void moveZeroes(vector<int>& nums) { int len = nums.size(); int j = 0; for (int i = 0; i < len; i ++) { if (nums[i] != 0) { swap(nums[i], nums[j ++]); } } } }; |
class Solution { public: void moveZeroes(vector<int>& nums) { int len = nums.size(); int j = 0; for (int i = 0; i < len; i ++) { if (nums[i] != 0) { swap(nums[i], nums[j ++]); } } } };
This is a O(n) loop and simply cannot be optimized further.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: CloudFlare Blocks Suspicious URL
Next Post: Self-Promoting Introduction to Job Posts - Algorithm Engineer