3875. 构造统一奇偶性数组 I

Easy

题目描述

给定一个由 n 个不同整数组成的数组 nums1。

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

对于每个索引 i，你必须从以下选择中恰好选择一个（顺序任意）：

• nums2[i] = nums1[i]
• nums2[i] = nums1[i] - nums1[j]，其中 j != i

如果可以构造这样的数组，返回 true，否则返回 false。

示例 1：

输入：nums1 = [2,3]
输出：true
解释：
选择 nums2[0] = nums1[0] - nums1[1] = 2 - 3 = -1。
选择 nums2[1] = nums1[1] = 3。
nums2 = [-1, 3]，两个元素都是奇数。因此答案是 true。

示例 2：

输入：nums1 = [4,6]
输出：true
解释：
选择 nums2[0] = nums1[0] = 4。
选择 nums2[1] = nums1[1] = 6。
nums2 = [4, 6]，所有元素都是偶数。因此答案是 true。

约束条件：

• 1 <= n == nums1.length <= 100
• 1 <= nums1[i] <= 100
• nums1 由不同的整数组成

提示：

• 只有一种可能的答案。

解题思路

这道题的关键在于理解奇偶性的数学规律。我们需要分析什么情况下能构造出全奇数或全偶数的数组。

核心观察：

1. 对于位置 i，我们可以选择 nums1[i] 或者 nums1[i] - nums1[j]（j ≠ i）
2. 两个数相减的奇偶性规律：
   • 奇数 - 奇数 = 偶数
   • 偶数 - 偶数 = 偶数
   • 奇数 - 偶数 = 奇数
   • 偶数 - 奇数 = 奇数

分析可能的情况：

• 如果数组中既有奇数又有偶数，那么我们总能通过减法操作得到奇数或偶数
• 如果数组全是奇数，我们可以选择保持原数（奇数）或者两个奇数相减（偶数）
• 如果数组全是偶数，我们可以选择保持原数（偶数）或者两个偶数相减（偶数）

通过数学分析可以发现，唯一无解的情况是：数组长度为1且该元素与目标奇偶性不符。但由于题目保证"只有一种可能的答案"，这意味着对于所有给定的测试用例都存在解。

因此，这道题的答案恒为 true。

代码实现

class Solution {
public:
    bool uniformArray(vector<int>& nums1) {
        return true;
    }
};

class Solution:
    def uniformArray(self, nums1: list[int]) -> bool:
        return True

public class Solution {
    public bool UniformArray(int[] nums1) {
        return true;
    }
}

/**
 * @param {number[]} nums1
 * @return {boolean}
 */
var uniformArray = function(nums1) {
    return true;
};

复杂度分析