Google+ Followers

Friday, October 2, 2015

[Leetcode] Move Zeroes, Solution

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:
  1. You must do this in-place without making a copy of the array.
  2. Minimize the total number of operations.

[Thoughts]
典型的双指针问题。使用两个指针遍历数组,一个指向数值为0的元素,另一个指向数值不为0的元素,在遍历的过程中,不断交换两个指针的值。

例如,

比较简单的一道题。

[Code]
1:  class Solution {  
2:  public:  
3:    void moveZeroes(vector<int>& nums) {  
4:      for(int zero_index = 0, none_zero_index = 0;  
5:        none_zero_index < nums.size() && zero_index < nums.size();   
6:      ) {  
7:        if(nums[zero_index] != 0) {  
8:          zero_index++;  
9:          none_zero_index = zero_index;  
10:          continue;  
11:        }   
12:        if(nums[none_zero_index] == 0) {  
13:          none_zero_index++;  
14:          continue;  
15:        }  
16:        int temp = nums[zero_index];  
17:        nums[zero_index] = nums[none_zero_index];  
18:        nums[none_zero_index] = temp;  
19:        zero_index++;  
20:        none_zero_index++;  
21:      }  
22:    }  
23:  };  

git: https://github.com/codingtmd/leetcode/blob/master/src/Move_Zeroes.cpp




Post a Comment