You are given an array nums1 of n distinct integers.
You want to construct another array nums2 of length n such that the elements in nums2 are either all odd or all even.
For each index i, you must choose exactly one of the following (in any order):
nums2[i] = nums1[i]
nums2[i] = nums1[i] - nums1[j], for an index j != i, such that nums1[i] - nums1[j] >= 1
Return true if it is possible to construct such an array, otherwise return false.
Example 1:
Input: nums1 = [1,4,7]
Output: true
Explanation:
Set nums2[0] = nums1[0] = 1.
Set nums2[1] = nums1[1] - nums1[0] = 4 - 1 = 3.
Set nums2[2] = nums1[2] = 7.
nums2 = [1, 3, 7], and all elements are odd. Thus, the answer is true.
Example 2:
Input: nums1 = [2,3]
Output: false
Explanation:
It is not possible to construct nums2 such that all elements have the same parity. Thus, the answer is false.
Example 3:
Input: nums1 = [4,6]
Output: true
Explanation:
Set nums2[0] = nums1[0] = 4.
Set nums2[1] = nums1[1] = 6.
nums2 = [4, 6], and all elements are even. Thus, the answer is true.
Constraints:
1 <= n == nums1.length <= 10^5
1 <= nums1[i] <= 10^9
nums1 consists of distinct integers.
今天這題跟昨天差不多，但是沒那麼白爛可以奇偶校驗後 return true。
題目給我們一條 nums1 裡面只有正整數，
問我們能不能透過這條 nums1 及兩條規則湊出合法的 nums2。
規則：
- nums2[i] == nums1[i]
- nums2[i] == nums[i] - nums[j]，nums[i] - nums[j] >= 1 && j != i
最終整條 nums2 都是奇數或是偶數即可合法。
昨天沒有那條 nums[i] - nums[j] >= 1，
有這條代表我們必須維護最小的奇數及偶數。
這題要考慮奇數變換為偶數的狀況，
奇數變換為偶數的狀況必然是奇數 i 要減去更小的奇數 j，
但是一但有奇數，最小的那個奇數找不到更小的奇數，
所以一但有奇數就湊不能偶數解答。
另偶數需要有更小奇數才能湊全奇數解答。
所以我們維護不須變換的兩個組合及奇偶變換的兩個組合，
總共四條組合即可。
C++程式碼：
假設 nums1 的長度為 N。
計算複雜度：O(N)
空間複雜度：O(1)
Github程式碼：
