Leetcode: Move Zeroes
LeetCode move
2023-09-11 14:14:07 时间
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]. Note: You must do this in-place without making a copy of the array. Minimize the total number of operations.
第二遍做法: 双指针压缩法:O(N), 空间:O(1)
实际上就是将所有的非0数向前尽可能的压缩,最后把没压缩的那部分全置0就行了。比如103040,先压缩成134,剩余的3为全置为0。过程中需要一个指针记录压缩到的位置。
1 public class Solution { 2 public void moveZeroes(int[] nums) { 3 if (nums==null || nums.length==0) return; 4 int cur=0; 5 for (int i=0; i<nums.length; i++) { 6 if (nums[i]!=0) { 7 nums[cur++] = nums[i]; 8 } 9 } 10 for (int i=cur; i<nums.length; i++) { 11 nums[i] = 0; 12 } 13 } 14 }
Q:如果要把所有的0放在前面而不是后面呢?
A:同样的解题思路,但是是从后向前遍历,将非0数字压缩到后面。
双指针同向法:O(N^2),不是太好
Two pointer l,r,
l is to find each 0 in the list, r is to start from l, find first non-0
l, r should not both start from 0, because if r is to the left of l, we don't want to swap it. example: [1, 0]
1 public class Solution { 2 public void moveZeroes(int[] nums) { 3 if (nums==null && nums.length==0) return; 4 int l=0, r=0; 5 while (l < nums.length && r < nums.length) { 6 while (l<nums.length && nums[l]!=0) { 7 l++; 8 } 9 r = l; 10 while (r<nums.length && nums[r]==0) { 11 r++; 12 } 13 if (l == nums.length || r == nums.length) break; 14 swap(nums, l, r); 15 } 16 } 17 18 public void swap(int[] nums, int l, int r) { 19 int temp = nums[l]; 20 nums[l] = nums[r]; 21 nums[r] = temp; 22 } 23 }
相关文章
- Leetcode: Find the Difference
- Leetcode: Longest Substring Without Repeating Characters
- Leetcode: Maximum Depth of Binary Tree
- LeetCode 724. 寻找数组的中心索引
- 148、【动态规划】leetcode ——63. 不同路径 II:递归法+迭代法(C++版本)
- leetcode - Interleaving String
- 【Leetcode】155: 最小栈(Python)
- [LeetCode] Find Anagram Mappings 寻找异构映射
- [LeetCode] Cherry Pickup 捡樱桃
- [LeetCode] Minimum Genetic Mutation 最小基因变化
- [LeetCode] 496. Next Greater Element I 下一个较大的元素之一
- [LeetCode] Move Zeroes 移动零
- [LeetCode] 131. Palindrome Partitioning 拆分回文串