LeetCode 解題筆記：3876. Construct Uniform Parity Array II

作者：王一哲
日期：2026年9月3日


LeetCode 題目連結：3876. Construct Uniform Parity Array II

解題想法

中等難度的題目，3875. Construct Uniform Parity Array I 的加強版。題目給一個長度為 $n$ 的陣列 $nums1$，從 $nums1$ 依序出數字組成全為奇數或偶數的陣列 $nums2$，而要必須符合以下 2 項要求的其中一項：

1. $nums2[i] = nums1[i]$​​​​​​​
2. $nums2[i] = nums1[i] - nums1[j], j \neq i, nums1[i] - nums1[j] \geq 1$

我一開始的解法比較直接，先將 $nums1$ 之中的奇數、偶數分別存入串列 odd_nums、even_nums，如果所有的數字都是奇數或偶數回傳 True；反之，每個偶數要找到一個比自己小的奇數，如果找不到回傳 False，如果所有的數字都能找到一個對應的數字，回傳 True。但是這樣的解法速度有點慢，後來發現這個要求可以簡化成 $nums1$ 的最小值是奇數，或是所有的數字都是偶數。

Python 程式碼

Runtime: 135 ms, beats 13.41%. Memory: 36.14 MB, beats 6.71%.

from bisect import bisect_left

class Solution:
    def uniformArray(self, nums1: list[int]) -> bool:
        # 讀取測資，奇數、偶數分別存入串列
        n = len(nums1)
        even_nums = []
        odd_nums = []
        for num in nums1:
            if num % 2 == 0:
                even_nums.append(num)
            else:
                odd_nums.append(num)
        
        # 特例，全是奇數或偶數
        if len(even_nums) == n or len(odd_nums) == n:
            return True
        
        # 一般狀況，每個偶數要找到一個比自己小的奇數
        odd_nums.sort()
        m = len(odd_nums)
        for num in even_nums:
            idx = bisect_left(odd_nums, num)
            if idx == m: idx -= 1
            while idx >= 0 and  odd_nums[idx] > num:
                idx -= 1
            if idx == -1:
                return False
        return True

Runtime: 9 ms, beats 92.68%. Memory: 36.29 MB, beats 73.17%.

from bisect import bisect_left

class Solution:
    def uniformArray(self, nums1: list[int]) -> bool:
        # 如果最小的數字是奇數或是全為偶數，回傳 True
        return min(nums1) % 2 == 1 or all(num % 2 == 0 for num in nums1)

C++ 程式碼

Runtime: 64 ms, beats 23.56%. Memory: 182.85 MB, beats 8.11%.

class Solution {
public:
    bool uniformArray(vector<int>& nums1) {
        // 讀取測資，奇數、偶數分別存入陣列
        size_t n = nums1.size();
        vector<int> even_nums, odd_nums;
        for(int num : nums1) {
            if (num % 2 == 0) even_nums.push_back(num);
            else odd_nums.push_back(num);
        }

        // 特例，全是奇數或偶數
        if (even_nums.size() == n || odd_nums.size() == n) {
            return true;
        }

        // 一般狀況，每個偶數要找到一個比自己小的奇數
        sort(odd_nums.begin(), odd_nums.end());
        int m = (int)odd_nums.size();
        for(int num : even_nums) {
            int idx = lower_bound(odd_nums.begin(), odd_nums.end(), num) - odd_nums.begin();
            if (idx == m) idx--;
            while(idx >= 0 && odd_nums[idx] > num) idx--;
            if (idx == -1) return false;
        }
        return true;
    }
};

Runtime: 4 ms, beats 65.18%. Memory: 165.90 MB, beats 62.83%.

class Solution {
public:
    bool uniformArray(vector<int>& nums1) {
        // 如果最小的數字是奇數或是全為偶數，回傳 True
        int imin = 1000000001;
        bool all_even = true;
        for(int num : nums1) {
            if (num < imin) imin = num;
            if (num % 2 == 1) all_even = false;
        }
        return (imin % 2 == 1) || all_even;
    }
};

C 語言程式碼

Runtime: 0 ms, beats 100.00%. Memory: 20.45 MB, beats 20.00%.

bool uniformArray(int* nums1, int nums1Size) {
    // 如果最小的數字是奇數或是全為偶數，回傳 True
    int imin = 1000000001;
    bool all_even = true;
    for(int i = 0; i < nums1Size; i++) {
        int num = nums1[i];
        if (num < imin) imin = num;
        if (num % 2 == 1) all_even = false;
    }
    return (imin % 2 == 1) || all_even;
}