Easy

题目描述

给定一个整数数组 nums。按照以下指定顺序对 nums 执行操作来转换数组：

  1. 将每个偶数替换为 0
  2. 将每个奇数替换为 1
  3. 将修改后的数组按非递减顺序排序

返回执行这些操作后的结果数组。

示例 1：

输入：nums = [4,3,2,1]
输出：[0,0,1,1]
解释：
- 将偶数（4 和 2）替换为 0，奇数（3 和 1）替换为 1。现在，nums = [0, 1, 0, 1]
- 按非递减顺序排序后，nums = [0, 0, 1, 1]

示例 2：

输入：nums = [1,5,1,4,2]
输出：[0,0,1,1,1]
解释：
- 将偶数（4 和 2）替换为 0，奇数（1, 5 和 1）替换为 1。现在，nums = [1, 1, 1, 0, 0]
- 按非递减顺序排序后，nums = [0, 0, 1, 1, 1]

约束条件：

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 1000

提示： 设偶数个数为 x，奇数个数为 y。输出 x 个 0，然后输出 y 个 1。

解题思路

这道题有两种常见的解法思路：

方法一：直接模拟 按照题目要求的步骤进行：先遍历数组将偶数替换为0、奇数替换为1，然后对修改后的数组进行排序。这种方法直观易懂，时间复杂度为 O(n log n)，主要消耗在排序步骤。

方法二：计数优化（推荐） 观察题目的本质：最终结果一定是所有的0排在前面，所有的1排在后面。因此我们可以直接统计原数组中偶数和奇数的个数，然后构造结果数组：先放置对应个数的0，再放置对应个数的1。这种方法避免了排序操作，时间复杂度降低到 O(n)。

由于题目提示也指出了这个优化思路，我们采用计数方法作为最优解。具体步骤：

  1. 遍历原数组，统计偶数个数
  2. 创建结果数组，前半部分填充0（偶数个数个），后半部分填充1（剩余位置）

这种方法既高效又简洁，是最优解法。

代码实现

class Solution {
public:
    vector<int> transformArray(vector<int>& nums) {
        int evenCount = 0;
        for (int num : nums) {
            if (num % 2 == 0) {
                evenCount++;
            }
        }
        
        vector<int> result(nums.size());
        for (int i = 0; i < evenCount; i++) {
            result[i] = 0;
        }
        for (int i = evenCount; i < nums.size(); i++) {
            result[i] = 1;
        }
        
        return result;
    }
};

class Solution:
    def transformArray(self, nums: List[int]) -> List[int]:
        even_count = sum(1 for num in nums if num % 2 == 0)
        return [0] * even_count + [1] * (len(nums) - even_count)

public class Solution {
    public int[] TransformArray(int[] nums) {
        int evenCount = 0;
        foreach (int num in nums) {
            if (num % 2 == 0) {
                evenCount++;
            }
        }
        
        int[] result = new int[nums.Length];
        for (int i = 0; i < evenCount; i++) {
            result[i] = 0;
        }
        for (int i = evenCount; i < nums.Length; i++) {
            result[i] = 1;
        }
        
        return result;
    }
}

var transformArray = function(nums) {
    return nums.map(num => num % 2).sort();
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
计数法O(n)O(1)
直接模拟O(n log n)O(1)

其中 n 为数组长度。计数法只需要一次遍历统计偶数个数，然后直接构造结果；而直接模拟需要额外的排序步骤。空间复杂度都是 O(1)（不考虑输出数组的空间）。

相关题目