Tuesday, October 4, 2016

283. Move Zeroes

Simple two pointers problem. We can have two pointers i and j. i is pointing to the next element in the array to check and j is pointing to the first 0 position. So for example [0, 0, 0, 1, 2]
1st round, i = 0, j = 0: 0, 0, 0, 1, 2
2nd round, i = 1, j = 0: 0, 0, 0, 1, 2
3rd round, i = 2, j = 0: 0, 0, 0, 1, 2
4th round, i = 3, j = 0: 1, 0, 0, 0, 2
5th round, i = 4, j = 1, 1, 2, 0, 0, 0

Another example, [1, 0, 3]
1st round, i = 0, j = 0: 1, 0, 3
2nd round, i = 1, j = 1: 1, 0, 3
3rd round, i = 2, j = 1: 1, 3, 0

1:  class Solution {  
2:  public:  
3:    void moveZeroes(vector<int>& nums) {  
4:      int i = 0, j = 0;  
5:      while (i < nums.size()) {  
6:        if (nums[i] == 0) {  
7:          i++;  
8:        } else {  
9:          swap(nums[i++], nums[j++]);  
10:        }  
11:      }  
12:    }  
13:  };  

No comments:

Post a Comment