来源:力扣(LeetCode)
链接: https://leetcode.cn/problems/move-zeroes
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
请注意 ,必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
提示:
统计非0的个数
:遍历一遍,统计非0元素的个数,并将非0元素往左拉;从后面开始遍历第二遍,基于长度差将末尾元素设置为0新建数组
:新建全0元素,并将非0元素在前面赋值双指针
:双指针,用j表示非0元素的位置,用下标i遍历数组,如果发现i下的元素非0,就将该元素赋值给j,如果i与j不相等,表明发生了挪动,此时需要将i处的元素设置为0;j++操作python实现
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# 方法1 统计0的个数,非0元素往前拉,末尾补零
"""
n = len(nums)
j = 0
for i in range(n):
if nums[i]:
nums[j] = nums[i]
j += 1
for i in range(j, n):
nums[i] = 0
return nums
c++实现
class Solution {
public:
void moveZeroes(vector<int>& nums) {
// 方法1 统计非0元素的个数,并将非零元素往左拉,并将末尾元素设置为0
int n = nums.size();
int j = 0;
for(int i=0; i<n; i++)
{
if(nums[i] != 0)
{
nums[j] = nums[i];
j++;
}
}
for(int i=j; i<n; i++)
{
nums[i] = 0;
}
};
复杂度分析
python实现
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# 方法2 开新数组,非0元素放入,0元素放末尾, 方法不行,因为需要在不复制数组情况下进行原地处理
n = len(nums)
new_nums = [0] * n
j = 0
for num in nums:
if num:
new_nums[j] = num
j += 1
return new_nums
c++实现
class Solution {
public:
void moveZeroes(vector<int>& nums) {
// 方法2 新建全0元素,并将非0元素在前面赋值;
int n = nums.size();
int j = 0;
vector <int> new_nums(n);
for(int i=0; i<n; i++)
{
if(nums[i] != 0)
{
new_nums[j] = nums[i];
j++;
}
}
nums = new_nums;
}
};
复杂度分析
由于新建数组
python实现
import copy
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# 方法3 直接在数组中进行index操作,用j记录非0元素的位置,并将非0元素挪动到j位置下,如果i与j不相等的话,将i置为0
n = len(nums)
j = 0
for i in range(n):
if nums[i]:
nums[j] = nums[i]
if i != j:
nums[i] = 0
j += 1
return nums
c++实现
class Solution {
public:
void moveZeroes(vector<int>& nums) {
// 方法3 双指针,用j表示非0元素的index,如果index i上的元素非0,就赋值该元素到index j下,如果i与j不相等,表明发生了移动,此时将i上的元素赋值为0
int n = nums.size();
int j = 0;
for(int i=0; i<n; i++)
{
if(nums[i] != 0)
{
nums[j] = nums[i];
if(i != j)
{
nums[i] = 0;
}
j++;
}
}
}
};
复杂度分析