Medium
题目描述
给定一个整数数组 nums。
如果对于每个索引 i（其中 0 <= i < n - 1），nums[i] 和 nums[i + 1] 具有不同的奇偶性（一个是偶数，另一个是奇数），则数组被称为奇偶性交替。
在一次操作中，你可以选择任意索引 i，并将 nums[i] 增加 1 或减少 1。
返回一个长度为 2 的整数数组 answer，其中：
answer[0]是使数组成为奇偶性交替所需的最少操作数。answer[1]是在所有可以通过执行恰好answer[0]次操作得到的奇偶性交替数组中，max(nums) - min(nums)的最小可能值。
长度为 1 的数组被认为是奇偶性交替的。
示例 1：
输入：nums = [-2,-3,1,4]
输出：[2,6]
解释：
应用以下操作：
- 将 nums[2] 增加 1，得到 nums = [-2, -3, 2, 4]。
- 将 nums[3] 减少 1，得到 nums = [-2, -3, 2, 3]。
结果数组是奇偶性交替的，max(nums) - min(nums) = 3 - (-3) = 6 是所有使用恰好 2 次操作得到的奇偶性交替数组中的最小可能值。
示例 2：
输入：nums = [0,2,-2]
输出：[1,3]
解释：
应用以下操作：
- 将 nums[1] 减少 1，得到 nums = [0, 1, -2]。
结果数组是奇偶性交替的，max(nums) - min(nums) = 1 - (-2) = 3 是所有使用恰好 1 次操作得到的奇偶性交替数组中的最小可能值。
示例 3：
输入：nums = [7]
输出：[0,0]
解释：
不需要操作。数组已经是奇偶性交替的，max(nums) - min(nums) = 7 - 7 = 0，这是最小可能值。
约束条件：
1 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9
解题思路
这道题需要分析奇偶性交替数组的特点。奇偶性交替数组只有两种模式：
- 偶数开头：偶数-奇数-偶数-奇数…
- 奇数开头：奇数-偶数-奇数-偶数…
解题思路：
对于每种模式，我们需要计算：
- 需要多少次操作才能使所有位置都符合要求的奇偶性
- 在最少操作次数的前提下，如何调整使得
max - min最小
关键观察：
- 如果某个位置的奇偶性不正确，必须改变 ±1 来修正奇偶性
- 对于需要修改的元素，我们可以选择 +1 或 -1，但要考虑如何最小化最终的极差
算法步骤：
尝试两种模式（偶数开头和奇数开头）
对于每种模式，计算需要修改的位置数量
对于需要修改的位置，贪心地选择调整方向：
- 如果元素较大，尽量减小（选择使其奇偶性正确的较小值）
- 如果元素较小，尽量增大（选择使其奇偶性正确的较大值）
- 这样可以最小化最终的极差
选择操作数最少的模式，如果操作数相同，选择极差更小的模式
代码实现
class Solution {
public:
vector<int> makeParityAlternating(vector<int>& nums) {
int n = nums.size();
if (n == 1) return {0, 0};
auto solve = [&](int startParity) -> pair<int, int> {
vector<int> modified = nums;
int operations = 0;
for (int i = 0; i < n; i++) {
int expectedParity = (startParity + i) % 2;
if (nums[i] % 2 != expectedParity) {
operations++;
// Choose +1 or -1 to minimize range
if (nums[i] % 2 == 0) {
// Need odd, choose +1 or -1
modified[i] = nums[i] + 1;
} else {
// Need even, choose +1 or -1
modified[i] = nums[i] + 1;
}
}
}
// Now optimize to minimize max - min
for (int i = 0; i < n; i++) {
int expectedParity = (startParity + i) % 2;
if (nums[i] % 2 != expectedParity) {
if (expectedParity == 0) {
// Need even
if (nums[i] % 2 == 1) {
modified[i] = nums[i] - 1; // or +1, choose optimally
}
} else {
// Need odd
if (nums[i] % 2 == 0) {
modified[i] = nums[i] + 1; // or -1, choose optimally
}
}
}
}
// Try both +1 and -1 for each position and choose optimally
vector<pair<int, int>> choices;
for (int i = 0; i < n; i++) {
int expectedParity = (startParity + i) % 2;
if (nums[i] % 2 != expectedParity) {
if (expectedParity == 0) {
// Need even: nums[i] is odd
choices.push_back({nums[i] - 1, nums[i] + 1});
} else {
// Need odd: nums[i] is even
choices.push_back({nums[i] - 1, nums[i] + 1});
}
} else {
choices.push_back({nums[i], nums[i]});
}
}
int minRange = INT_MAX;
function<void(int, vector<int>&)> dfs = [&](int idx, vector<int>& current) {
if (idx == n) {
int maxVal = *max_element(current.begin(), current.end());
int minVal = *min_element(current.begin(), current.end());
minRange = min(minRange, maxVal - minVal);
return;
}
if (choices[idx].first == choices[idx].second) {
current[idx] = choices[idx].first;
dfs(idx + 1, current);
} else {
current[idx] = choices[idx].first;
dfs(idx + 1, current);
current[idx] = choices[idx].second;
dfs(idx + 1, current);
}
};
if (operations <= 20) { // Only use DFS for small number of changes
vector<int> current(n);
dfs(0, current);
return {operations, minRange};
} else {
// Greedy approach for large operations
for (int i = 0; i < n; i++) {
if (choices[i].first != choices[i].second) {
modified[i] = choices[i].first; // Choose the smaller one initially
} else {
modified[i] = choices[i].first;
}
}
int maxVal = *max_element(modified.begin(), modified.end());
int minVal = *min_element(modified.begin(), modified.end());
return {operations, maxVal - minVal};
}
};
auto result1 = solve(0); // Start with even
auto result2 = solve(1); // Start with odd
if (result1.first < result2.first) {
return {result1.first, result1.second};
} else if (result2.first < result1.first) {
return {result2.first, result2.second};
} else {
return {result1.first, min(result1.second, result2.second)};
}
}
};
class Solution:
def makeParityAlternating(self, nums: List[int]) -> List[int]:
n = len(nums)
if n == 1:
return [0, 0]
def solve(start_parity):
operations = 0
choices = []
for i in range(n):
expected_parity = (start_parity + i) % 2
if nums[i] % 2 != expected_parity:
operations += 1
if expected_parity == 0:
# Need even: nums[i] is odd
choices.append((nums[i] - 1, nums[i] + 1))
else:
# Need odd: nums[i] is even
choices.append((nums[i] - 1, nums[i] + 1))
else:
choices.append((nums[i], nums[i]))
# Find minimum range
if operations <= 20:
min_range = float('inf')
def dfs(idx, current):
nonlocal min_range
if idx == n:
min_range = min(min_range, max(current) - min(current))
return
if choices[idx][0] == choices[idx][1]:
current.append(choices[idx][0])
dfs(idx + 1, current)
current.pop()
else:
current.append(choices[idx][0])
dfs(idx + 1, current)
current.pop()
current.append(choices[idx][1])
dfs(idx + 1, current)
current.pop()
dfs(0, [])
return operations, min_range
else:
# Greedy approach
modified = []
for i in range(n):
if choices[i][0] != choices[i][1]:
modified.append(choices[i][0])
else:
modified.append(choices[i][0])
return operations, max(modified) - min(modified)
ops1, range1 = solve(0)
ops2, range2 = solve(1)
if ops1 < ops2:
return [ops1, range1]
elif ops2 < ops1:
return [ops2, range2]
else:
return [ops1, min(range1, range2)]
public class Solution {
public int[] MakeParityAlternating(int[] nums) {
int n = nums.Length;
if (n == 1) return new int[] {0, 0};
var solve = new Func<int, (int, int)>(startParity => {
int operations = 0;
var choices = new List<(int, int)>();
for (int i = 0; i < n; i++) {
int expectedParity = (startParity + i) % 2;
if (nums[i] % 2 != expectedParity) {
operations++;
if (expectedParity == 0) {
choices.Add((nums[i] - 1, nums[i] + 1));
} else {
choices.Add((nums[i] - 1, nums[i] + 1));
}
} else {
choices.Add((nums[i], nums[i]));
}
}
if (operations <= 20) {
int minRange = int.MaxValue;
void Dfs(int idx, List<int> current) {
if (idx == n) {
minRange = Math.Min(minRange, current.Max() - current.Min());
return;
}
if (choices[idx].Item1 == choices[idx].Item2) {
current.Add(choices[idx].Item1);
Dfs(idx + 1, current);
current.RemoveAt(current.Count - 1);
} else {
current.Add(choices[idx].Item1);
Dfs(idx + 1, current);
current.RemoveAt(current.Count - 1);
current.Add(choices[idx].Item2);
Dfs(idx + 1, current);
current.RemoveAt(current.Count - 1);
}
}
Dfs(0, new List<int>());
return (operations, minRange);
} else {
var modified = new List<int>();
for (int i = 0; i < n; i++) {
modified.Add(choices[i].Item1);
}
return (operations, modified.Max() - modified.Min());
}
});
var (ops1, range1) = solve(0);
var (ops2, range2) = solve(1);
if (ops1 < ops2) {
return new int[] {ops1, range1};
} else if (ops2 < ops1) {
return new int[] {ops2, range2};
} else {
return new int[] {ops1, Math.Min(range1, range2)};
}
}
}
var makeParityAlternating = function(nums) {
if (nums.length === 1) return [0, 0];
function solve(startParity) {
let operations = 0;
let values = [];
for (let i = 0; i < nums.length; i++) {
let expectedParity = (startParity + i) % 2;
let currentParity = Math.abs(nums[i]) % 2;
if (currentParity === expectedParity) {
values.push(nums[i]);
} else {
operations++;
values.push(nums[i] + (nums[i] >= 0 ? 1 : -1));
}
}
let minVal = Math.min(...values);
let maxVal = Math.max(...values);
return [operations, maxVal - minVal];
}
let result1 = solve(0); // start with even
let result2 = solve(1); // start with odd
if (result1[0] < result2[0]) {
return result1;
} else if (result1[0] > result2[0]) {
return result2;
} else {
return [result1[0], Math.min(result1[1], result2[1])];
}
};
复杂度分析
| 指标 | 复杂度 |
|---|---|
| 时间 | - |
| 空间 | - |