Leetcode—283Move Zeroes-白红宇

Leetcode—283Move Zeroes

阅读量：4136 次

发布时间：2019-05-25

本文共 1310 字，大约阅读时间需要 4 分钟。

题目：

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

Note:

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

Minimize the total number of operations.

解答

两种解法

我自己的写的，
用两个指针i,j分别指向0和非0的，如果i< j，交换i,j，i往前移动指向下一个0，j往前移动指向下一个非0；否则，也就是当i指向0，j指向非0时，如果i>j，那么j继续往前移动，跳过0（其实此时就是i），指向非0。
时间复杂度就是遍历一次数组，O(N)，AC，beats 92%。

class Solution {
  //用两个指针i,j分别指向0和非0的，如果i

& nums) { if(nums.size()<=1) return ; int len=nums.size(); int i=0,j=0; while(true) { while(nums[i]!=0&&i

i) swap(nums[i],nums[j]); else j++; } }private: void swap(int &a,int &b) { int c; c=a; a=b; b=c; }};

看了discussion之后，排名第二的，解法太amazing

class Solution {public:    void moveZeroes(vector
   
    & nums) {        int j = 0;        // move all the nonzero elements advance        for (int i = 0; i < nums.size(); i++) {            if (nums[i] != 0) {                nums[j++] = nums[i];            }        }        for (;j < nums.size(); j++) {            nums[j] = 0;        }    }};

非常容易理解！！！

转载地址：http://dexvi.baihongyu.com/

你可能感兴趣的文章

TitledBorder 设置JPanel边框