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?
We use two pointers $i$ and $j$, where pointer $i$ points to the end of the sequence that has been processed, and pointer $j$ points to the head of the sequence to be processed. Initially, $i=-1$.
Next, we traverse $j \in [0,n)$, if $nums[j] \neq 0$, then we swap the next number pointed by pointer $i$ with $nums[j]$, and move $i$ forward. Continue to traverse until $j$ reaches the end of the array, all non-zero elements of the array are moved to the front of the array in the original order, and all zero elements are moved to the end of the array.
The time complexity is $O(n)$, where $n$ is the length of the array $nums$. The space complexity is $O(1)$.
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
i = -1
for j, x in enumerate(nums):
if x:
i += 1
nums[i], nums[j] = nums[j], nums[i]
class Solution {
public void moveZeroes(int[] nums) {
int i = -1, n = nums.length;
for (int j = 0; j < n; ++j) {
if (nums[j] != 0) {
int t = nums[++i];
nums[i] = nums[j];
nums[j] = t;
}
}
}
}
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int i = -1, n = nums.size();
for (int j = 0; j < n; ++j) {
if (nums[j]) {
swap(nums[++i], nums[j]);
}
}
}
};
func moveZeroes(nums []int) {
i := -1
for j, x := range nums {
if x != 0 {
i++
nums[i], nums[j] = nums[j], nums[i]
}
}
}
/**
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++;
}
}
}
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;
}
}
}
}
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var moveZeroes = function (nums) {
let i = -1;
for (let j = 0; j < nums.length; ++j) {
if (nums[j]) {
const t = nums[++i];
nums[i] = nums[j];
nums[j] = t;
}
}
};
void moveZeroes(int* nums, int numsSize) {
int i = 0;
for (int j = 0; j < numsSize; j++) {
if (nums[j] != 0) {
if (j > i) {
nums[i] = nums[j];
nums[j] = 0;
}
i++;
}
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。