一起学算法-905.按奇偶排序数组

一、题目

LeetCode-905. 按奇偶排序数组
链接：https://leetcode-cn.com/problems/sort-array-by-parity/

难度：简单
给定一个非负整数数组A返回一个数组，在该数组中， A的所有偶数元素之后跟着所有奇数元素。

你可以返回满足此条件的任何数组作为答案。

示例：
输入：[3,1,2,4]
输出：[2,4,3,1]
输出 [4,2,3,1]，[2,4,1,3] 和 [4,2,1,3] 也会被接受。

提示：

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

二、解题思路

从题意中我们可知，只要把偶数移动到数组左边，而奇数在右边即可，并不考虑数的大小顺序。
本题虽然说是排序，但是根据其特点可以用双指针来求解。
创建两个指针left和right分别指向数组的头和尾，根据left和right指针指向的奇偶性来做出操作，具体有四种情况；

1. (1,0)，交换两个数，并且left++,right--；
2. (0,1)，左右两边的数都不用动，left++,right--；
3. (0,0)，说明left的位置是正确的，只能left++；
4. (1,1)，说明right的位置是正确的，只能right--；

按照思路我们优先判断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不太好看，根据四种情况优化一下代码。

三、实现过程

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;
};

四、小结

1. 时间复杂度：O(N)，N是数组的长度。
2. 空间复杂度：O(1)