Easy

题目描述

给你一个整数数组 nums，将数组中的所有偶数元素移动到数组的前面，后跟所有奇数元素。

返回满足此条件的任一数组作为答案。

示例 1：

输入：nums = [3,1,2,4]
输出：[2,4,3,1]
解释：[4,2,3,1]、[2,4,1,3] 和 [4,2,1,3] 也会被接受。

示例 2：

输入：nums = [0]
输出：[0]

提示：

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

解题思路

这道题要求将数组按奇偶性重新排列，偶数在前，奇数在后。有多种解法可以实现：

解法一：双指针（原地交换）- 推荐

使用左右双指针，左指针从头开始寻找奇数，右指针从尾开始寻找偶数。当左指针指向奇数且右指针指向偶数时，交换两个元素。这样可以在一次遍历中完成排序，时间复杂度O(n)，空间复杂度O(1)。

解法二：新建数组

创建新数组，先遍历一遍将所有偶数加入，再遍历一遍将所有奇数加入。虽然实现简单，但需要额外的O(n)空间。

解法三：内置排序

使用自定义比较器，让偶数的优先级高于奇数。时间复杂度O(n log n)，不如双指针高效。

双指针解法最优，既保持了线性时间复杂度，又是原地操作，空间效率最佳。

代码实现

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        
        while (left < right) {
            // 左指针找奇数
            if (nums[left] % 2 == 0) {
                left++;
            }
            // 右指针找偶数
            else if (nums[right] % 2 == 1) {
                right--;
            }
            // 找到了一对需要交换的元素
            else {
                swap(nums[left], nums[right]);
                left++;
                right--;
            }
        }
        
        return nums;
    }
};

class Solution:
    def sortArrayByParity(self, nums: List[int]) -> List[int]:
        left, right = 0, len(nums) - 1
        
        while left < right:
            # 左指针找奇数
            if nums[left] % 2 == 0:
                left += 1
            # 右指针找偶数
            elif nums[right] % 2 == 1:
                right -= 1
            # 找到了一对需要交换的元素
            else:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1
        
        return nums

public class Solution {
    public int[] SortArrayByParity(int[] nums) {
        int left = 0, right = nums.Length - 1;
        
        while (left < right) {
            // 左指针找奇数
            if (nums[left] % 2 == 0) {
                left++;
            }
            // 右指针找偶数
            else if (nums[right] % 2 == 1) {
                right--;
            }
            // 找到了一对需要交换的元素
            else {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
                right--;
            }
        }
        
        return nums;
    }
}

var sortArrayByParity = function(nums) {
    let left = 0;
    let right = nums.length - 1;
    
    while (left < right) {
        if (nums[left] % 2 === 0) {
            left++;
        } else if (nums[right] % 2 === 1) {
            right--;
        } else {
            [nums[left], nums[right]] = [nums[right], nums[left]];
            left++;
            right--;
        }
    }
    
    return nums;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型双指针解法
时间复杂度O(n)
空间复杂度O(1)

相关题目