题目

3875. 构造奇偶一致的数组 I

给你一个长度为 n 的数组 nums1，其中包含 互不相同 的整数。

你需要构造另一个长度为 n 的数组 nums2，使得 nums2 中的元素要么全部为奇数，要么全部为偶数。

对于每个下标 i，你必须从以下两种选择中任选其一（顺序不限）：

  1. nums2[i] = nums1[i]
  2. nums2[i] = nums1[i] - nums1[j]，其中 j ≠ i

如果可以构造出满足条件的数组 nums2，返回 true；否则返回 false。

示例 1：

1
2
3
输入：nums1 = [2,3]
输出：true
解释：nums2[0] = 2 - 3 = -1（奇数），nums2[1] = 3（奇数）。nums2 = [-1, 3] 全为奇数。

示例 2：

1
2
3
输入：nums1 = [4,6]
输出：true
解释：nums2[0] = 4，nums2[1] = 6。nums2 = [4, 6] 全为偶数。

提示：

  • 2 <= n <= 100
  • -10^5 <= nums1[i] <= 10^5

思路

奇偶性的三条运算规则

这道题的核心完全在于奇偶性分析，先回忆三条基础规则：

1
2
3
奇 ± 奇 = 偶
偶 ± 偶 = 偶
奇 ± 偶 = 奇

减法在奇偶性上和加法完全等价，因为 -奇 = 奇、-偶 = 偶。

对每个位置能输出什么？

对于数组中任意一个元素 nums1[i]，我们来分析它通过两种操作能输出什么奇偶性。

情况一：nums1[i] 是偶数

操作 表达式 结果奇偶
选项1：保留自身 nums1[i] 偶数
选项2：减去偶数 偶 - 偶 偶数
选项2：减去奇数 偶 - 奇 奇数

结论：偶数位置既能输出偶数，也能输出奇数。

情况二：nums1[i] 是奇数

操作 表达式 结果奇偶
选项1：保留自身 nums1[i] 奇数
选项2：减去奇数 奇 - 奇 偶数
选项2：减去偶数 奇 - 偶 奇数

结论：奇数位置既能输出奇数，也能输出偶数。

三种场景的统一结论

综合以上分析，无论数组是什么情况：

数组情况 策略 结果
全部为奇数 全部保留自身 → 全奇 true
全部为偶数 全部保留自身 → 全偶 true
奇偶混合 每个位置都能自由选择奇偶性 → 总能构造出全奇或全偶 true

答案永远是 true！

举例验证

例：nums1 = [2, 3]（奇偶混合）

目标全奇：nums2[0] = 2 - 3 = -1（奇），nums2[1] = 3（奇）→ 成功。

目标全偶：nums2[0] = 2（偶），nums2[1] = 3 - 3… 不行，j ≠ i。nums2[1] = 3 - 2 = 1（奇）。等等，3 只能输出奇？

让我们重新审视 nums1 = [2, 3] 中奇数 3 的情况：

  • 3 是奇数，自身 = 奇
  • 3 - 2 = 奇 - 偶 = 奇

哦！当数组中只有一个偶数时，奇数 3 无法通过减法变成偶数（唯一可减的 2 是偶数，奇 - 偶 = 奇）。

那反过来，偶数 2 能变成什么？

  • 2 是偶数，自身 = 偶
  • 2 - 3 = 偶 - 奇 = 奇

所以 2 既能变偶也能变奇，但 3 只能是奇数。

这意味着：

  • 想全偶？3 不行 → 失败
  • 想全奇？2 可以变成 2-3 = -1（奇），3 本身就是奇 → 成功 ✓

依然返回 true，只是只有全奇这条路走得通。

什么情况下会返回 false？

通过上面的分析你可能会发现：不管怎么组合，似乎总有一条路能走通。让我们更严谨地推导：

什么时候全偶不可能？
→ 存在某个奇数元素 x，且数组中没有其他奇数可以让它相减（奇 - 奇 = 偶）。
→ 即：数组中恰好有一个奇数，其余全为偶数。

此时这个”孤独的奇数”：

  • 自身是奇数
  • 减去任何偶数 = 奇数
    → 它只能是奇数，无法变成偶数。

什么时候全奇不可能？
→ 存在某个偶数元素 y，且数组中没有其他偶数可以让它相减（偶 - 偶 = 偶 不行，我们需要 偶 - 奇 = 奇）。
→ 等等，偶数想变成奇数需要 偶 - 奇 = 奇。只要数组中存在至少一个奇数，偶数就能通过减去那个奇数变成奇数！
→ 所以全奇不可能的情况是：数组中没有奇数（全偶）——但全偶时直接保留自身就是全偶了，不需要全奇。

关键洞察：全偶和全奇是两条独立的路。我们只需要至少一条路走通即可：

  • 如果数组全奇或全偶：保留自身，直接成功。
  • 如果数组混合奇偶：
    • 若奇数 ≥ 2：每个奇数都能找另一个奇数相减变偶 → 全偶可行 → true
    • 若恰好一个奇数（其余全偶）：这个奇数无法变偶 → 全偶不可行。但偶数可以减去这个唯一的奇数变奇 → 全奇可行 → true

无论哪种情况，总有一条路走通。答案确实永远是 true。

复杂度分析

  • 时间复杂度：O(1)，不需要任何遍历。
  • 空间复杂度：O(1)。

代码

1
2
3
4
5
class Solution {
    public boolean uniformArray(int[] nums1) {
        return true;
    }
}

相关疑问

这算数学题吗？

是的，而且是非常纯粹的数学题。 它考察的是整数奇偶性的基本运算规律（加减不改变奇偶性规则），以及能否严谨地分类讨论穷尽所有情况。代码只有一行 return true，但背后的数学推理才是这道题的核心。

这算脑筋急转弯吗？

有点像！ 这道题的”反直觉”之处在于：

  • 初看题目，你可能会想：”这要怎么构造？是不是要遍历找方案？”
  • 深入分析奇偶性后才发现：无论输入什么，总有解。
  • 这就像一个”陷阱题”——题目描述得像是需要复杂构造，但数学推理告诉你答案恒为 true。

不过它不是无厘头的脑筋急转弯，而是一道**有扎实数学支撑的”结论题”**。类似的题目还有很多，比如：

“给定任意整数数组，总能通过 + 或 - 让所有元素变成偶数吗？”（答案也是总能，因为 a + a = 2a 必为偶…不过这道更简单）

真正的”脑筋急转弯”式算法题，本质上都是：你以为需要计算，但数学证明告诉你答案是常量。

和 CodeForces 原题的区别

值得一提的是，这道题的原型来自 CodeForces，原题有一个额外约束：构造出的 nums2 每个元素都必须大于 0。加上这个约束后，return true 就不再正确了，需要根据最小值的奇偶性来判断。LeetCode 版本去掉了正数约束，使得解法简化为恒 true。

关键点

  1. 奇偶性不变性：减法和加法在奇偶性上等价，因为负号不改变奇偶性。
  2. 分类讨论的完备性：分析”偶数能输出什么”和”奇数能输出什么”时，需要穷尽减去奇数和减去偶数两种可能。
  3. 两条路的独立性：题目要求全奇 或 全偶，只要有一条路能走通就算成功，不需要两条都通。
  4. 孤独的奇数：当数组中只有一个奇数时，它无法变成偶数（因为没有另一个奇数让它相减），但此时全奇这条路依然走得通（偶数可以减这个奇数变奇）。

相关题目