日期：2026年9月3日
LeetCode 題目連結：3876. Construct Uniform Parity Array II
解題想法
中等難度的題目，3875. Construct Uniform Parity Array I 的加強版。題目給一個長度為 $n$ 的陣列 $nums1$，從 $nums1$ 依序出數字組成全為奇數或偶數的陣列 $nums2$，而要必須符合以下 2 項要求的其中一項：
- $nums2[i] = nums1[i]$
- $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)
