[Leetcode] Sort Array By Parity(Easy)

發表於： 分類於：
字數： 228 閱讀：≈ 1分鐘 瀏覽：

LeetCode 905 - Sort Array By Parity

Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers.

Return any array that satisfies this condition.

example:

Input: nums = [3,1,2,4]
Output: [2,4,3,1]
Explanation: The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Input: nums = [0]
Output: [0]

How can we solve this problem?

這個問題很簡單，就是把偶數移動到Array的前面，基數移動到後面。我們這裡可以使用Two-pointer approach, i為尋找前面的基數，而j 為尋找後面的偶數，只要nums[i]為基數,nums[j]為偶數就進行交換。

Solution: 

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& nums) {
        int i = 0;
        int j = nums.size() - 1;
        
        //O(n)
        while(i < j){
            //i is even skip
            //j is odd skip
            //i is odd and j is even swap
            if(nums[i] % 2 == 0) i++;
            else if(nums[j] % 2 == 1) j--;
            else swap(nums[i++],nums[j--]);
        }
        return nums;
    }
};