前缀和+后缀和数组(有兴趣可以自己用前缀和算出后缀和,则只需要一个数组)
时间复杂度 $O(n)$
// 以被删除元素为分界点,前面的奇偶不变,后面元素位置的奇偶颠倒
// first:和被删除元素位置奇偶相同的元素和
// 由2部分组成:
// 1. pre[i + 1] - val,是被删除元素前面,位置奇偶性相同元素的前缀和
// 2. suf[i + 1],是被删除元素后面,和被删除元素奇偶性相反元素的后缀和,删除元素后,由于奇偶性颠倒
// 和被删元素奇偶性相同
// second:和被删除元素位置奇偶性相反的元素和
// 由2部分组成:
// 1. pre[i],被删元素前一个元素所在序列的前缀和
// 2. suf[i] - val,是被删除元素后面,和被删除元素奇偶性相同元素的后缀和,删除元素后,由于奇偶性颠倒
// 和被删元素奇偶性恰好相反
C++ 代码 (奇偶数组版)
class Solution {
public:
int waysToMakeFair(vector<int>& nums) {
int len = nums.size();
int pre[len + 1], suf[len + 1];
pre[0] = 0, suf[len] = 0;
for(int i = 1; i <= len; i++)
pre[i] = nums[i - 1] + (i - 2 >= 0 ? pre[i - 2] : 0);
for(int i = len - 1; i >= 0; i--)
suf[i] = nums[i] + (i + 2 <= len ? suf[i + 2] : 0);
int cnt = 0;
for(int i = 0; i < len; i++)
{
int val = nums[i];
int first = pre[i + 1] - val + suf[i + 1];
int second = pre[i] + suf[i] - val;
if(first == second) cnt++;
}
return cnt;
}
};
C++代码(单数组版,emmm比开2个数组复杂。。。)
class Solution {
public:
// 前面的奇偶不变,后面的奇偶替换
int waysToMakeFair(vector<int>& nums) {
int len = nums.size();
int pre[len + 1];
pre[0] = 0;
for(int i = 1; i <= len; i++)
pre[i] = nums[i - 1] + (i - 2 >= 0 ? pre[i - 2] : 0);
int cnt = 0;
for(int i = 0; i < len; i++)
{
int val = nums[i];
int end = (len - 1 - i) & 1 ? len - 2 : len - 1;
// 不同的末尾
int first = pre[i + 1] - val + pre[(len - 1 - i) & 1 ? end + 2 : end] - pre[i];
// 相同的末尾
int second = pre[i] + pre[end + 1] - pre[i + 1];
if(first == second) cnt++;
}
return cnt;
}
};