一、題目

LeetCode-905. 按奇偶排序數(shù)組
鏈接：https://leetcode-cn.com/problems/sort-array-by-parity/

難度：簡單
給定一個(gè)非負(fù)整數(shù)數(shù)組A返回一個(gè)數(shù)組，在該數(shù)組中， A的所有偶數(shù)元素之后跟著所有奇數(shù)元素。

你可以返回滿足此條件的任何數(shù)組作為答案。

示例：
輸入：[3,1,2,4]
輸出：[2,4,3,1]
輸出 [4,2,3,1]，[2,4,1,3] 和 [4,2,1,3] 也會(huì)被接受。

提示：

• 1 <= A.length <= 5000
• 0 <= A[i] <= 5000

二、解題思路

從題意中我們可知，只要把偶數(shù)移動(dòng)到數(shù)組左邊，而奇數(shù)在右邊即可，并不考慮數(shù)的大小順序。
本題雖然說是排序，但是根據(jù)其特點(diǎn)可以用雙指針來求解。
創(chuàng)建兩個(gè)指針left和right分別指向數(shù)組的頭和尾，根據(jù)left和right指針指向的奇偶性來做出操作，具體有四種情況；

1. (1,0)，交換兩個(gè)數(shù)，并且left++,right--；
2. (0,1)，左右兩邊的數(shù)都不用動(dòng)，left++,right--；
3. (0,0)，說明left的位置是正確的，只能left++；
4. (1,1)，說明right的位置是正確的，只能right--；

按照思路我們優(yōu)先判斷left位置的奇偶性，順著思路寫出以下代碼。

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& nums) {
        int left = 0,right = nums.size() - 1;
        while(left < right){
            if(nums[left]%2 == 1){
                if(nums[right]%2 == 0){
                    swap(nums[left],nums[right]);
                    left++;
                    right--;
                }else{
                    right--;
                }
            }else{
                left++;
            }
        }
        return nums;
    }
};

嵌套if不太好看，根據(jù)四種情況優(yōu)化一下代碼。

三、實(shí)現(xiàn)過程

c++

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& nums) {
        int left = 0,right = nums.size() - 1;
        while(left < right){
            if (nums[left] % 2 > nums[right] % 2) swap(nums[left],nums[right]);
            if (nums[left] % 2 == 0) left++;
            if (nums[right] % 2 == 1) right--;
        }
        return nums;
    }
};

PHP

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer[]
     */
    function sortArrayByParity($nums) {
        $left = 0;
        $right = count($nums) - 1;
        while($left < $right){
            if ($nums[$left] % 2 > $nums[$right] % 2) {
                $tmp = $nums[$left];
                $nums[$left] = $nums[$right];
                $nums[$right] = $tmp;
            }
            if ($nums[$left] % 2 == 0) $left++;
            if ($nums[$right] % 2 == 1) $right--;
        }
        return $nums;
    }
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArrayByParity = function(nums) {
        let left = 0,right = nums.length - 1;
        while(left < right){
            if (nums[left] % 2 > nums[right] % 2) {
                let tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp;
            }
            if (nums[left] % 2 == 0) left++;
            if (nums[right] % 2 == 1) right--;
        }
        return nums;
};

四、小結(jié)

1. 時(shí)間復(fù)雜度：O(N)，N是數(shù)組的長度。
2. 空間復(fù)雜度：O(1)