LeetCode 283 Move Zeros

Problem:

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].

1. You must do this in-place without making a copy of the array.

2. Minimize the total number of operations.

Summary:

在不复制数组的情况下，将整型数组中的所有0移至数组末尾，其他数相对位置不变。

尽可能减少操作数。

Analysis：

1. 常规方法：用两个指针，其中一个指针向后扫，每找到一个非零元素则与前面指针内容互换。

 class Solution {

 public:

     void moveZeroes(vector<int>& nums) {

         int len = nums.size(), k = ;

         for (int i = ; i < len; i++) {

             if (nums[i] != ) {

                 swap(nums[i], nums[k++]);

             }

         }

         return;

     }

 };

但由于交换操作过多，导致效率不高。

2. 同样两个指针，其中一个指针向后扫，每找到一个非零元素则按顺序从数组头往后放，另一个指针记录当前放置位置。

　第一个指针扫完时，将第二个指针到数组末尾全部填0即可。

 class Solution {

 public:

     void moveZeroes(vector<int>& nums) {

         int len = nums.size(), k = ;

         for (int i = ; i < len; i++) {

             if (nums[i] != ) {

                 nums[k++] = nums[i];

             }

         }

         while (k < len) {

             nums[k++] = ;

         }

         return;

     }

 };

巴特西

LeetCode 283 Move Zeros

最新文章

热门文章