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.
方法一:直接遍历,一个个的把0往后面调整(但是有一个问题就是时间复杂度太高,leetcode不予通过) 比如说: [0,1,0,3,12] 看左边的 元素是否为零,右边的元素是否不为0,如果是这样的情况,就进行交换 并且一次循环只交换一次,再重新遍历 [1,0,0,3,12] [1,0,3,0,12] [1,3,0,0,12] [1,3,0,12,0] [1,3,12,0,0] 什么时候结束这个外层循环呢?
void moveZeroes(int* nums, int numsSize){
//一步一步的去移动,改变顺序
while(true)
{
//int count = 0;
bool isOk = true;
//对数组进行遍历
for(int i = 0;i<numsSize-1;i++)
{
//左边的数字等于0,右边的数字不等0,那么就进行交换
if(nums[i]==0&&nums[i+1]!=0)
{
//count++;
isOk =false;
int t = nums[i];
nums[i] = nums[i+1];
nums[i+1] = t;
break;
}
}
//if(count == 0)
if(isOk)
{
break;
}
}
}
改进: 去掉while循环,外层改用for循环,因为外侧需要循环的次数就是这个元素的个数,大不了0在最前面,类似于冒泡排序
void moveZeroes(int* nums, int numsSize){
for(int j = 1;j<=numsSize;j++)
{
for(int i = 0;i<numsSize-1;i++)
{
//左边的数字等于0,右边的数字不等0,那么就进行交换
if(nums[i]==0&&nums[i+1]!=0)
{
int t = nums[i];
nums[i] = nums[i+1];
nums[i+1] = t;
}
}
}
}
方法二:直接写答案 定义一个变量j=0,在遍历数组的时候,这个数组元素的值不为0的时候,就让nums[j]=nums[i],结束之后,再再里面补0即可。
void moveZeroes(int* nums, int numsSize){
int j = 0;
for(int i =0;i<numsSize;i++)
{
if(nums[i] != 0)
{
nums[j++] = nums[i];
}
}
//开始补0
for(j = j;j<numsSize;j++)
{
nums[j]=0;
}
}
方法三:重新给一个数组
void moveZeroes(int* nums, int numsSize){
int arr[numsSize];
int j=0;
for(int i =0;i<numsSize;i++)
{
if(nums[i] != 0)
{
arr[j++] = nums[i];
}
}
//开始补0
while(j<numsSize)
{
arr[j]=0;
}
for(int i = 0;i<numsSize;i++)
{
nums[i] = arr[i];
}
}
可是leetcode时间过不去。。。 枯了
python版本
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
j = 0
for i in range(len(nums)):
if nums[i]!=0:
nums[j] = nums[i]
j +=1
while (j <len(nums)):
nums[j] = 0
j +=1