What is the main strategy behind the "Transform Array by Parity" problem?

The main strategy is to sort the array such that all even numbers appear before the odd numbers while maintaining their relative order.

How can I solve this problem with minimal space?

You can solve this problem in-place using a two-pointer technique to partition the array without extra space.

Is there a more efficient approach than sorting?

Yes, counting the even and odd numbers and then reconstructing the array can achieve linear time complexity, which is more efficient than sorting.

What is the time complexity of the sorting solution?

The time complexity of the sorting-based solution is O(n log n), where n is the size of the array.

How does GhostInterview help in solving this problem?

GhostInterview guides you through multiple approaches, helps avoid common mistakes, and prepares you for the interviewer's signals on array manipulation problems.

#3467

Easy

auto_awesome数组·排序

LeetCode 题解工作台

将数组按照奇偶性转化

给你一个整数数组 nums 。请你按照以下顺序依次执行操作，转换 nums ：将每个偶数替换为 0。将每个奇数替换为 1。按非递减顺序排序修改后的数组。执行完这些操作后，返回结果数组。示例 1: 输入： nums = [4,3,2,1] 输出： [0,0,1,1] 解释：将偶数（…

数组排序计数

题目描述

给你一个整数数组 nums。请你按照以下顺序依次执行操作，转换 nums：

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

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

示例 1:

输入：nums = [4,3,2,1]

输出：[0,0,1,1]

解释：

将偶数（4 和 2）替换为 0，将奇数（3 和 1）替换为 1。现在，nums = [0, 1, 0, 1]。
按非递减顺序排序 nums，得到 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，得到 nums = [0, 0, 1, 1, 1]。

提示：

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

lightbulb

解题思路

方法一：计数

我们可以遍历数组 $\textit{nums}$ ，统计其中偶数的个数 $\textit{even}$ 。然后我们将数组的前 $\textit{even}$ 个元素置为 $0$ ，剩余的元素置为 $1$ 。

时间复杂度 $O(n)$ ，其中 $n$ 是数组 $\textit{nums}$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

class Solution:
    def transformArray(self, nums: List[int]) -> List[int]:
        even = sum(x % 2 == 0 for x in nums)
        for i in range(even):
            nums[i] = 0
        for i in range(even, len(nums)):
            nums[i] = 1
        return nums

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate understands sorting and partitioning techniques.
question_mark
Candidate demonstrates knowledge of array manipulation and space efficiency.
question_mark
Candidate is able to explain the impact of different approaches on time complexity.

warning

常见陷阱

外企场景

error
Confusing the order of even and odd numbers during implementation.
error
Forgetting to maintain the relative order of even and odd numbers.
error
Relying on inefficient sorting techniques when a linear time solution is possible.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change the constraints to allow for larger array sizes.
arrow_right_alt
Add constraints on the range of values for nums.
arrow_right_alt
Require that the array be sorted in descending order after partitioning.

help

常见问题

外企场景

继续练习

#3267 统计近似相等数对 II #3265 统计近似相等数对 I #3186 施咒的最大总伤害