9.3【A】

3876

不一样的在于规则二上只能选择当前位置之前的数来构造

依旧假设，

如果要构造奇数，如果当前位置是奇数，则没事，如果为偶数，则前面位置必须出现过奇数，否则当前位置上的偶数无法消除掉

然后如果要构造偶数，若当前位置为奇数，则前面必须出现过奇数，如果为偶数，没事

所以关键在于当前位置的前面是否出现过奇数

那验证的话，

能否一次遍历合并起来·？

考虑全奇数和全偶数

如果第一个数为奇数，那么为True

如果第一个数为偶数，那么出现第一个奇数的时候，就无法构造，返回false

所以就是验证，第一个奇数前面是否有偶数，如果是的话，那么为false，否则为true

不对，审错题了，不是i和j的关系，而是数组数值间的关系，即nums[i]必须要比j大个1或以上

不过应该可以排序来转出出来

这样的复杂度是排序

题解

这个是关键洞察，即数组最小值决定最终奇偶性

这个题解的思想和我的差不多，只不过更数学化规范化，即判断第一个数之间的关系

只不过题解的关键洞察，能够找到更本质的，就是最小值决定奇偶，也就是排序后的第一个数

代码流程，标志是否出现过奇数和偶数，然后在相同的一次遍历当中，去找到最小值