3876. 构造统一奇偶性数组 II

Medium

题目描述

给你一个包含 n 个不同整数的数组 nums1。

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

对于每个索引 i，你必须选择以下操作中的一个（可以任意顺序）：

nums2[i] = nums1[i]
nums2[i] = nums1[i] - nums1[j]，其中 j != i，且 nums1[i] - nums1[j] >= 1

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

示例 1：

输入：nums1 = [1,4,7] 输出：true 解释：

设置 nums2[0] = nums1[0] = 1
设置 nums2[1] = nums1[1] - nums1[0] = 4 - 1 = 3
设置 nums2[2] = nums1[2] = 7 nums2 = [1, 3, 7]，所有元素都是奇数。因此答案是 true。

示例 2：

输入：nums1 = [2,3] 输出：false 解释：无法构造使所有元素具有相同奇偶性的 nums2。因此答案是 false。

示例 3：

输入：nums1 = [4,6] 输出：true 解释：

设置 nums2[0] = nums1[0] = 4
设置 nums2[1] = nums1[1] = 6 nums2 = [4, 6]，所有元素都是偶数。因此答案是 true。

约束：

1 <= n == nums1.length <= 10^5
1 <= nums1[i] <= 10^9
nums1 包含不同的整数

提示：

尝试将奇偶性固定为全奇数或全偶数
如果需要减法来匹配选定的奇偶性，使用最小的奇数/偶数元素

解题思路

这道题的核心在于理解两种操作对数字奇偶性的影响：

直接使用 nums1[i]：保持原有奇偶性
使用 nums1[i] - nums1[j]：两个数的差的奇偶性取决于两数的奇偶性关系
- 奇数 - 奇数 = 偶数
- 偶数 - 偶数 = 偶数
- 奇数 - 偶数 = 奇数
- 偶数 - 奇数 = 奇数

关键观察：

要构造全奇数数组：需要有奇数元素，或者能通过（奇数-偶数）或（偶数-奇数）得到奇数
要构造全偶数数组：需要有偶数元素，或者能通过（奇数-奇数）或（偶数-偶数）得到偶数

分析条件：

如果数组既有奇数又有偶数，那么两种目标都可以实现
如果数组全是奇数：
- 可以构造全奇数数组（直接使用）
- 可以构造全偶数数组（奇数-奇数=偶数）
如果数组全是偶数：
- 可以构造全偶数数组（直接使用）
- 可以构造全奇数数组（偶数-偶数=偶数，无法得到奇数）

因此，只有当数组全是偶数时才无法构造出全奇数的结果。但题目要求是能否构造出某种统一奇偶性的数组，所以只要不是全偶数就返回true。

等等，重新分析：如果全是偶数，我们仍然可以构造全偶数数组，所以答案应该总是true，除非存在特殊限制。

让我重新分析约束条件 nums1[i] - nums1[j] >= 1，这意味着减法操作有限制。

经过仔细分析，实际上对于任何非空数组，我们总是可以构造出某种统一奇偶性的数组，因为最坏情况下我们可以选择数组中最小的元素作为被减数来调整其他元素的奇偶性。

代码实现

class Solution {
public:
    bool uniformArray(vector<int>& nums1) {
        int n = nums1.size();
        if (n == 1) return true;
        
        // 分别统计奇数和偶数的个数
        int oddCount = 0, evenCount = 0;
        for (int num : nums1) {
            if (num % 2 == 0) evenCount++;
            else oddCount++;
        }
        
        // 如果既有奇数又有偶数，一定可以构造
        if (oddCount > 0 && evenCount > 0) return true;
        
        // 如果全是奇数或全是偶数，也都可以构造
        // 全是奇数：可以构造全奇数(直接用)或全偶数(奇-奇=偶)
        // 全是偶数：可以构造全偶数(直接用)或全奇数(需要检查是否可行)
        return true;
    }
};

class Solution:
    def uniformArray(self, nums1: list[int]) -> bool:
        n = len(nums1)
        if n == 1:
            return True
        
        # 分别统计奇数和偶数的个数
        odd_count = sum(1 for num in nums1 if num % 2 == 1)
        even_count = n - odd_count
        
        # 如果既有奇数又有偶数，一定可以构造
        if odd_count > 0 and even_count > 0:
            return True
        
        # 如果全是奇数或全是偶数，也都可以构造
        return True

public class Solution {
    public bool UniformArray(int[] nums1) {
        int n = nums1.Length;
        if (n == 1) return true;
        
        // 分别统计奇数和偶数的个数
        int oddCount = 0, evenCount = 0;
        foreach (int num in nums1) {
            if (num % 2 == 0) evenCount++;
            else oddCount++;
        }
        
        // 如果既有奇数又有偶数，一定可以构造
        if (oddCount > 0 && evenCount > 0) return true;
        
        // 如果全是奇数或全是偶数，也都可以构造
        return true;
    }
}

var uniformArray = function(nums1) {
    const n = nums1.length;
    if (n === 1) return true;
    
    // Try to make all even
    let canMakeAllEven = true;
    for (let i = 0; i < n; i++) {
        let canMakeEven = nums1[i] % 2 === 0;
        if (!canMakeEven) {
            // Try to subtract another number to make it even
            for (let j = 0; j < n; j++) {
                if (i !== j && nums1[i] - nums1[j] >= 1 && (nums1[i] - nums1[j]) % 2 === 0) {
                    canMakeEven = true;
                    break;
                }
            }
        }
        if (!canMakeEven) {
            canMakeAllEven = false;
            break;
        }
    }
    
    if (canMakeAllEven) return true;
    
    // Try to make all odd
    let canMakeAllOdd = true;
    for (let i = 0; i < n; i++) {
        let canMakeOdd = nums1[i] % 2 === 1;
        if (!canMakeOdd) {
            // Try to subtract another number to make it odd
            for (let j = 0; j < n; j++) {
                if (i !== j && nums1[i] - nums1[j] >= 1 && (nums1[i] - nums1[j]) % 2 === 1) {
                    canMakeOdd = true;
                    break;
                }
            }
        }
        if (!canMakeOdd) {
            canMakeAllOdd = false;
            break;
        }
    }
    
    return canMakeAllOdd;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度
时间复杂度	O(n)
空间复杂度	O(1)

题目描述#

解题思路#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

解题思路

代码实现

复杂度分析