Easy

题目描述

给定一个非负整数数组 nums，nums 中一半整数是奇数，一半整数是偶数。

对数组进行排序，以便当 nums[i] 为奇数时，i 也是奇数；当 nums[i] 为偶数时， i 也是偶数。

返回任何满足此条件的答案数组。

示例 1：

输入：nums = [4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5], [2,5,4,7], [2,7,4,5] 也会被接受。

示例 2：

输入：nums = [2,3]
输出：[2,3]

约束：

  • 2 <= nums.length <= 2 * 10^4
  • nums.length 是偶数
  • nums 中一半的整数是偶数
  • 0 <= nums[i] <= 1000

进阶： 你能原地解决这个问题吗？

解题思路

解题思路

这道题要求我们将数组重新排列，使得偶数位置（0, 2, 4…）放偶数，奇数位置（1, 3, 5…）放奇数。

方法一：额外数组法

  • 创建一个新数组，用两个指针分别指向偶数位置和奇数位置
  • 遍历原数组，将偶数放到偶数位置，奇数放到奇数位置
  • 时间复杂度 O(n)，空间复杂度 O(n)

方法二：双指针原地交换法（推荐）

  • 使用两个指针 i 和 j，分别指向偶数位置和奇数位置
  • i 从 0 开始，每次增加 2，寻找偶数位置上的奇数
  • j 从 1 开始，每次增加 2，寻找奇数位置上的偶数
  • 当找到不匹配的元素时，交换它们
  • 这种方法实现了原地排序，空间复杂度为 O(1)

核心思想是利用题目保证的条件：数组中一半是奇数，一半是偶数，因此通过双指针交换一定能找到正确的配对。

代码实现

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        int i = 0, j = 1;
        int n = nums.size();
        
        while (i < n && j < n) {
            // 寻找偶数位置上的奇数
            while (i < n && nums[i] % 2 == 0) {
                i += 2;
            }
            // 寻找奇数位置上的偶数
            while (j < n && nums[j] % 2 == 1) {
                j += 2;
            }
            // 交换不匹配的元素
            if (i < n && j < n) {
                swap(nums[i], nums[j]);
            }
        }
        
        return nums;
    }
};

class Solution:
    def sortArrayByParityII(self, nums: List[int]) -> List[int]:
        i, j = 0, 1
        n = len(nums)
        
        while i < n and j < n:
            # 寻找偶数位置上的奇数
            while i < n and nums[i] % 2 == 0:
                i += 2
            # 寻找奇数位置上的偶数
            while j < n and nums[j] % 2 == 1:
                j += 2
            # 交换不匹配的元素
            if i < n and j < n:
                nums[i], nums[j] = nums[j], nums[i]
        
        return nums

public class Solution {
    public int[] SortArrayByParityII(int[] nums) {
        int i = 0, j = 1;
        int n = nums.Length;
        
        while (i < n && j < n) {
            // 寻找偶数位置上的奇数
            while (i < n && nums[i] % 2 == 0) {
                i += 2;
            }
            // 寻找奇数位置上的偶数
            while (j < n && nums[j] % 2 == 1) {
                j += 2;
            }
            // 交换不匹配的元素
            if (i < n && j < n) {
                (nums[i], nums[j]) = (nums[j], nums[i]);
            }
        }
        
        return nums;
    }
}

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

复杂度分析

复杂度类型双指针原地交换法额外数组法
时间复杂度O(n)O(n)
空间复杂度O(1)O(n)

说明：

  • 时间复杂度：每个元素最多被访问常数次，总体为 O(n)
  • 空间复杂度：双指针法只使用常数额外空间，额外数组法需要 O(n) 空间

相关题目