奇偶统一数组构造问题，简单题看思路：力扣3876

问题描述

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

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

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

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

问题分析

奇偶性分析

首先，我们只关心数字的奇偶性，因为目标是让所有数同奇偶。

关键约束：nums1[i] – nums1[j] >= 1，即 nums1[i] > nums1[j]。

核心观察

设数组中的最小值为 mn。

情况一：最小值为奇数

• 最小值 mn 本身是奇数，直接保留即可。

• 对于数组中的任意偶数 x：

  • 因为 x > mn（互不相同且 mn 最小）

  • 我们可以令 j 为最小值的位置，则 x – mn 是 奇数（偶 – 奇 = 奇）

  • 且 x – mn >= 1 成立

• 对于数组中的任意奇数，直接保留即可。

结论：如果最小值为奇数，一定可以构造成功。

情况二：最小值为偶数

• 最小值 mn 是偶数，无法通过减去某个数变成奇数（因为偶数 – 任何数 = 奇数，需要减奇数，但数组中没有比它小的奇数）。

• 因此，所有数必须都是偶数才能成功。

• 如果数组中存在奇数：

  • 这个奇数无法变成偶数：

    • 奇数 – 偶数 = 奇数（不行）

    • 奇数 – 奇数 = 偶数，但需要找一个更小的奇数，而最小值已经是偶数，不存在更小的奇数

  • 所以失败。

结论：如果最小值为偶数，则必须数组中全是偶数才能成功。

三种代码实现对比

版本一：直观实现 //这是我看出了题的意思后的解法，耗时比官解长

class Solution {
public:
bool uniformArray(vector<int>& nums1) {
int minx = INT_MAX;
for (auto a : nums1) {
minx = min(a, minx);
}
int jiou = minx % 2; // 1:奇数, 0:偶数

for (int i = 0; i < nums1.size(); i++) {
if (nums1[i] % 2 != jiou) { // 奇偶性不同
if (jiou) { // 最小值是奇数
if (nums1[i] > minx) {
continue; // 可以减去最小值变成奇数
}
}
return false;
}
}
return true;
}
};

分析：

• 逻辑正确，但代码不够简洁

• 可读性一般，需要理解 jiou 的含义

版本二：位运算优化 //这是我看了官解后优化的位运算，因为之前的一章中也提及了位运算可以加快速度于是做了优化

class Solution {
public:
bool uniformArray(vector<int>& nums1) {
int minx = INT_MAX;
for (auto a : nums1) {
minx = min(a, minx);
}
int jiou = minx & 1;

for (int i = 0; i < nums1.size(); i++) {
if ((nums1[i] & 1) != jiou) {
if (jiou) {
if (nums1[i] > minx) {
continue;
}
}
return false;
}
}
return true;
}
};

版本三：简洁优雅的正确实现

class Solution {
public:
bool uniformArray(vector<int>& nums1) {
int mn = nums1[0];
bool hasOdd = false; //官解非常巧妙，遍历一次，设计标记是否有奇数

for (int v : nums1) {
if (v < mn) {
mn = v;
}
if (v & 1) {
hasOdd = true;
}
}

if (mn & 1) {
return true; // 最小值为奇数，一定成功
}
return !hasOdd; // 最小值为偶数，必须没有奇数
}
};

优点：

• 逻辑清晰，与数学分析完全对应

• 时间复杂度 O(n)，空间复杂度 O(1)

• 代码简洁，易于维护

正确性证明

充分性

必要性

总结