第 494 场周赛Q1+Q2：101018. 构造奇偶一致的数组 I+101020. 构造奇偶一致的数组 II

题目链接：

101018. 构造奇偶一致的数组 I（简单）

101020. 构造奇偶一致的数组 II（中等）

算法原理：

👉对应力扣题解

解法：分类讨论

Ⅰ题

0ms击败100.00%

时间复杂度O(1)

我们发现最终的数组中可以存在负数，同时负数的奇偶数也算在内

分类讨论：

①全是偶数→返回true

②全是奇数→返回true

③同时存在偶数和奇数：一定可构造成全奇数

比如nums=[2,3]

如果构造成全偶数：需要让3变成偶数，但奇数-偶数=奇数：3-2=1，因此构造成全偶数不可能

如果构造成全奇数：需要让2变成奇数，偶数-奇数=奇数：2-3=-1，可以→返回true

再举个例子nums=[2,3,5]

如果构造成全偶数：3→-2：3-5，5→2：5-3，最终构造出[2,-2,2]→返回true

如果构造成全奇数：2-3=-1或2-5=-3均可，最终构造出[-1,3,5]或[-3,3,5]→返回true

还有别的情况吗？没了！因此最终结果一定为true，直接返回true

Ⅱ题

105ms击败11.65%

时间复杂度O(N logN)

Ⅱ题在Ⅰ题上加了限制：最终的数组中不能存在负数

①全是偶数→返回true

②全是奇数→返回true

③同时存在偶数和奇数：排序后第一个数是奇数→返回true

整体思路：

最小的数不能改(保证非负)，且所有数都可以减最小的数(不减自己就行)，因此以最小的数的奇偶性来构造

奇数-偶数=奇数：例如[2,3]，3不可能变成偶数

偶数-奇数=奇数：例如[1,2]，2可以变成奇数

因此最终结果取决于排序后的第一个数:

是奇数→返回true

是偶数→返回false

优化

既然同时存在奇数和偶数时我们仅需判断最小数的奇偶性即可，那么我们可以用一次遍历来找最小数，避免使用高复杂度的排序

Java代码：

class Solution { //101018. 构造奇偶一致的数组 I public boolean uniformArray(int[] nums1) { return true; } }

class Solution { //101020. 构造奇偶一致的数组 II public boolean uniformArray(int[] nums1) { int cnt0=0,cnt1=0; for(int x:nums1){ if(x%2==0) cnt0++; else cnt1++; } //全是奇数或全是偶数就返回true if(cnt0==0||cnt1==0) return true; List<Integer> list=new ArrayList<>(); for(int x:nums1) list.add(x); Collections.sort(list); return list.get(0)%2==1; } }

class Solution { //101020. 构造奇偶一致的数组 II //优化 public boolean uniformArray(int[] nums1) { int cnt0=0,cnt1=0,mn=0x3f3f3f3f; for(int x:nums1){ mn=Math.min(x,mn); if(x%2==0) cnt0++; else cnt1++; } return cnt0==0||cnt1==0||mn%2==1; } }