题目

中文

https://leetcode-cn.com/problems/move-zeroes/submissions/
image.png

英文

https://leetcode.com/problems/move-zeroes/submissions/
283. Move Zeroes
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.
Note:

  1. You must do this in-place without making a copy of the array.
  2. Minimize the total number of operations.

relative adj. 相对的

题解

第一次

个人思考

遍历数组发现0则删除该元素但不改变数组大小 并使用一个变量记录0的个数。
最后给末尾元素补0 ——-数组不应该考虑删除
所以 直接遍历数组 如果有0则寻找下一个不是零的 交换 没有则没事
交换之后再继续向后移动。
时间复杂度应该是O(N^2)

  1. void moveZeroes(int *nums, int numsSize)
  2. {
  3.     for (int i = 0; i < numsSize; i++)
  4.     {
  5.         if (nums[i] == 0)
  6.         {
  7.             for (int j = i + 1; j < numsSize; j++)
  8.             {
  9.                 if (nums[j] != 0)
  10.                 {
  11.                     int temp;
  12.                     temp = nums[j];
  13.                     nums[j] = nums[i];
  14.                     nums[i] = temp;
  15.                     break;
  16.                 }
  17.             }
  18.         }
  19.     }
  20.     return nums;
  21. }

效率很低 下一次思考优化方法。
image.png

讲解-第二次

思路：不用二层遍历
使用一个变量 j来记录下一个非0元素存放的位置。
有0挪到后面。这样复杂度变成O(n)

void moveZeroes(int *nums, int numsSize)
{
    int j=0;//next non-negetive number location
    for (int i = 0; i < numsSize; i++)
    {
     if(nums[i]!=0){
         int temp;
         temp=nums[j];
         num[j]=nums[i];
         nums[i]=temp;
         j++;
     }   
    }
    return nums;
}

j来表示下一个非0元素位置

为什么不为0时要进行交换而不是直接赋值呢？
交换的话 当前位置数的值变成0 把非0元素放到了前面。
如果直接赋值的话，后面的部分还是原来的非0数字，最后应该加一次对后面元素赋值为0的操作。