三刷 06/2022
Version #1 Two Pointers
Time O(N)
Space O(1)
Runtime: 2 ms, faster than 76.88% of Java online submissions for Move Zeroes.
Memory Usage: 55 MB, less than 34.95% of Java online submissions for Move Zeroes.
class Solution {
public void moveZeroes(int[] nums) {
int start = 0;
int end = 0;
while (end < nums.length) {
if (nums[end] != 0) {
nums[start++] = nums[end];
}
end++;
}
while (start < nums.length) {
nums[start++] = 0;
}
}
}
二刷
Optimized number of operation
跟一刷相比，去掉了swap的操作
一直用fast指针覆盖slow指针的值
最后用0补齐slow to end
Runtime: 1 ms, faster than 100.00% of Java online submissions for Move Zeroes.
Memory Usage: 43.7 MB, less than 87.70% of Java online submissions for Move Zeroes.
class Solution {
public void moveZeroes(int[] nums) {
if (nums == null) {
return;
}
int slow = 0, fast = 0;
// slow is pointing to the first element that's not ordered
// fast if pointing to the 1st non-zero element on the right of slow
// s
// f
// [0,1,0,3,12]
// [1,1,0,3,12]
while (fast < nums.length) {
if (nums[fast] == 0) {
fast++;
continue;
}
if (slow != fast) {
nums[slow] = nums[fast];
}
slow++;
fast++;
}
while (slow < nums.length) {
nums[slow] = 0;
slow++;
}
}
}
一刷
Slow pointer is always the tail of our valid range.public class Solution {
public void moveZeroes(int[] nums) {
if (nums == null || nums.length == 0) return;
int slow = 0, fast = 0;
int temp;
while (fast < nums.length) {
if (nums[fast] != 0) {
temp = nums[fast];
nums[fast] = nums[slow];
nums[slow] = temp;
slow++;
}
fast++;
}
}
}
No comments:
Post a Comment