Medium
题目描述
给你一个整数数组 nums。你可以选择 恰好一个 下标（从 0 开始）并删除对应的元素。请注意，删除元素后，其他元素的下标可能会发生变化。
例如，如果 nums = [6,1,7,4,1]：
- 选择删除下标 1，结果为
nums = [6,7,4,1] - 选择删除下标 2，结果为
nums = [6,1,4,1] - 选择删除下标 4，结果为
nums = [6,1,7,4]
如果一个数组是 公平的，那么奇数下标元素的和等于偶数下标元素的和。
返回你可以选择的下标数目，使得删除对应元素后，nums 是公平的。
示例 1：
输入：nums = [2,1,6,4]
输出：1
解释：
删除下标 0：[1,6,4] -> 偶数和：1 + 4 = 5，奇数和：6。不公平。
删除下标 1：[2,6,4] -> 偶数和：2 + 4 = 6，奇数和：6。公平。
删除下标 2：[2,1,4] -> 偶数和：2 + 4 = 6，奇数和：1。不公平。
删除下标 3：[2,1,6] -> 偶数和：2 + 6 = 8，奇数和：1。不公平。
有 1 个下标可以删除使 nums 公平。
示例 2：
输入：nums = [1,1,1]
输出：3
解释：删除任何下标，剩余数组都是公平的。
示例 3：
输入：nums = [1,2,3]
输出：0
解释：删除任何下标后都无法使数组公平。
提示：
1 <= nums.length <= 10^51 <= nums[i] <= 10^4
解题思路
这道题的关键在于理解删除元素后，剩余元素的下标会发生重新排列。我们需要分析删除某个位置的元素后，新数组的奇偶位置元素和。
思路分析：
当我们删除位置 i 的元素后，原数组分为两部分：
- 位置
[0, i-1]的元素保持原有的奇偶性 - 位置
[i+1, n-1]的元素奇偶性会发生变化
具体来说，删除位置 i 后：
- 新的偶数位置和 = 原
[0, i-1]偶数位置和 + 原[i+1, n-1]奇数位置和 - 新的奇数位置和 = 原
[0, i-1]奇数位置和 + 原[i+1, n-1]偶数位置和
算法步骤：
- 预计算前缀和：分别计算到位置
i为止的偶数位置和与奇数位置和 - 对每个可能删除的位置
i，计算删除后的新偶数和与新奇数和 - 判断两者是否相等，如果相等则计数器加一
使用前缀和可以在 O(1) 时间内计算每个位置删除后的结果，总时间复杂度为 O(n)。
代码实现
class Solution {
public:
int waysToMakeFair(vector<int>& nums) {
int n = nums.size();
vector<int> evenPrefix(n + 1, 0), oddPrefix(n + 1, 0);
// 计算前缀和
for (int i = 0; i < n; i++) {
evenPrefix[i + 1] = evenPrefix[i];
oddPrefix[i + 1] = oddPrefix[i];
if (i % 2 == 0) {
evenPrefix[i + 1] += nums[i];
} else {
oddPrefix[i + 1] += nums[i];
}
}
int count = 0;
for (int i = 0; i < n; i++) {
// 删除位置i后，新的偶数和与奇数和
int newEvenSum = evenPrefix[i] + (oddPrefix[n] - oddPrefix[i + 1]);
int newOddSum = oddPrefix[i] + (evenPrefix[n] - evenPrefix[i + 1]);
if (newEvenSum == newOddSum) {
count++;
}
}
return count;
}
};
class Solution:
def waysToMakeFair(self, nums: List[int]) -> int:
n = len(nums)
even_prefix = [0] * (n + 1)
odd_prefix = [0] * (n + 1)
# 计算前缀和
for i in range(n):
even_prefix[i + 1] = even_prefix[i]
odd_prefix[i + 1] = odd_prefix[i]
if i % 2 == 0:
even_prefix[i + 1] += nums[i]
else:
odd_prefix[i + 1] += nums[i]
count = 0
for i in range(n):
# 删除位置i后，新的偶数和与奇数和
new_even_sum = even_prefix[i] + (odd_prefix[n] - odd_prefix[i + 1])
new_odd_sum = odd_prefix[i] + (even_prefix[n] - even_prefix[i + 1])
if new_even_sum == new_odd_sum:
count += 1
return count
public class Solution {
public int WaysToMakeFair(int[] nums) {
int n = nums.Length;
int[] evenPrefix = new int[n + 1];
int[] oddPrefix = new int[n + 1];
// 计算前缀和
for (int i = 0; i < n; i++) {
evenPrefix[i + 1] = evenPrefix[i];
oddPrefix[i + 1] = oddPrefix[i];
if (i % 2 == 0) {
evenPrefix[i + 1] += nums[i];
} else {
oddPrefix[i + 1] += nums[i];
}
}
int count = 0;
for (int i = 0; i < n; i++) {
// 删除位置i后，新的偶数和与奇数和
int newEvenSum = evenPrefix[i] + (oddPrefix[n] - oddPrefix[i + 1]);
int newOddSum = oddPrefix[i] + (evenPrefix[n] - evenPrefix[i + 1]);
if (newEvenSum == newOddSum) {
count++;
}
}
return count;
}
}
/**
* @param {number[]} nums
* @return {number}
*/
var waysToMakeFair = function(nums) {
const n = nums.length;
let evenSum = 0, oddSum = 0;
// Calculate total even and odd sums
for (let i = 0; i < n; i++) {
if (i % 2 === 0) {
evenSum += nums[i];
} else {
oddSum += nums[i];
}
}
let count = 0;
let leftEvenSum = 0, leftOddSum = 0;
for (let i = 0; i < n; i++) {
// Calculate sums after removing element at index i
let newEvenSum, newOddSum;
if (i % 2 === 0) {
// Removing an even-indexed element
newEvenSum = leftEvenSum + (oddSum - leftOddSum);
newOddSum = leftOddSum + (evenSum - leftEvenSum - nums[i]);
} else {
// Removing an odd-indexed element
newEvenSum = leftEvenSum + (oddSum - leftOddSum - nums[i]);
newOddSum = leftOddSum + (evenSum - leftEvenSum);
}
if (newEvenSum === newOddSum) {
count++;
}
// Update left sums
if (i % 2 === 0) {
leftEvenSum += nums[i];
} else {
leftOddSum += nums[i];
}
}
return count;
};
复杂度分析
| 复杂度类型 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 前缀和解法 | O(n) | O(n) |
复杂度分析：
- 时间复杂度： O(n)，需要遍历数组两次，一次计算前缀和，一次检查每个删除位置
- 空间复杂度： O(n)，需要额外的数组存储奇偶位置的前缀和