📘 題目敘述
給你一個長度為 n 的陣列
nums1，其中所有整數都互不相同。
你想要建出另一個長度也是 n 的陣列
nums2，並且讓
nums2 裡的元素要嘛全部都是奇數，要嘛全部都是偶數。
對每個 index i，你必須剛好從下面兩種方式中選一種來決定
nums2[i]：
nums2[i] = nums1[i]-
nums2[i] = nums1[i] - nums1[j]，其中j != i，且nums1[i] - nums1[j] >= 1
請回傳是否有可能建出這樣的 nums2。
條件限制
1 <= n == nums1.length <= 10^51 <= nums1[i] <= 10^9nums1中所有整數都互不相同
🧠 解題思路
這題本質上還是在看奇偶性。
差別是這次做差值時，必須滿足結果
>= 1，所以不能隨便拿一個數去減另一個數，而是只能用比較大的數減比較小的數。
因此排序之後，最小值會變得很重要。因為最小值不可能再透過減法變成別的奇偶性，它幾乎只能保留自己原本的奇偶性。
所以我先排序，然後看最小值是奇數還是偶數：
- 如果最小值是奇數，那我可以把整個陣列都做成奇數
- 如果最小值是偶數，那我只能檢查整個陣列是不是全偶數
最後就能直接判斷答案。
所有變數
nums1：輸入陣列i：掃描nums1時取出的元素值
🪜 主要流程步驟
1. 先把陣列排序
sort(nums1.begin(), nums1.end());
我先排序，因為這題多了一個條件：
nums1[i] - nums1[j] >= 1
這代表我只能用比較大的數去減比較小的數。
所以排序之後，nums1[0]
就是最小值，而它的奇偶性會直接影響整題能不能成功。
2. 如果最小值是奇數，答案一定是 true
if (nums1[0] % 2 == 1) {
return true;
}
這一步是整題最關鍵的判斷。
如果最小值是奇數，我就可以把整個 nums2 都做成奇數。
原因是：
- 如果某個數本來就是奇數，我可以直接保留它
- 如果某個數本來是偶數，因為最小值是奇數，而且它一定比最小值大，所以我可以用：
- 偶數 - 奇數 = 奇數
而且這個差值一定
>= 1，因為是比較大的數減比較小的數。
所以只要最小值是奇數，整體一定做得出來，直接回傳 true。
3. 如果最小值是偶數，就不能把全部做成奇數
最小值如果是偶數，它自己沒有辦法再透過減法變成奇數。
因為它已經是最小值了，找不到更小的數讓它去減，所以它只能：
- 直接保留自己
那它就一定還是偶數。
所以這種情況下，整個陣列不可能全部做成奇數。
因此我只剩下一條路可以試：
- 看能不能全部做成偶數
4. 如果最小值是偶數，那只要出現奇數就失敗
for (int i : nums1) {
if (i % 2 == 1) {
return false;
}
}
現在我要的是全偶數。
如果某個數本來就是偶數，那直接保留自己就好。
但如果某個數是奇數，它想變成偶數，就必須做：
- 奇數 - 奇數 = 偶數
也就是說，它前面必須要有一個更小的奇數可以給它減。
可是現在最小值已經是偶數了，表示整個陣列最前面根本不是奇數。
所以一旦陣列中出現奇數，就會有某個奇數找不到更小的奇數去配，整體就不可能全部變成偶數。
因此只要看到奇數，就直接回傳 false。
5. 如果一路都沒看到奇數，代表全偶數，答案就是 true
return true;
如果程式能走到這裡，表示：
- 最小值是偶數
- 而且整個陣列都沒有奇數
也就是說，整個陣列本來就全是偶數。
那我直接把每個位置都保留原值，就已經符合題目要求，所以答案是
true。
⏱️ 複雜度
設 n = nums1.length。
- 時間複雜度：
O(n log n)
主要花在排序，後面掃描一次是 O(n)。
- 空間複雜度：
O(1)
如果不計排序內部使用的額外空間，額外只用了固定變數。
💻 程式碼實作
class Solution {
public:
bool uniformArray(vector<int>& nums1) {
sort(nums1.begin(), nums1.end());
if (nums1[0] % 2 == 1) {
return true;
}
for (int i : nums1) {
if (i % 2 == 1) {
return false;
}
}
return true;
}
};
🔗 題目連結
https://leetcode.com/problems/construct-uniform-parity-array-ii/