题目描述
这是 LeetCode 上的 1005. K 次取反后最大化的数组和 ，难度为 简单。
Tag : 「优先队列（堆）」、「模拟」、「贪心」
给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
- 选择某个下标
i并将nums[i]替换为-nums[i]。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以这种方式修改数组后，返回数组 可能的最大和 。
示例 1：
输入：nums = [4,2,3], k = 1 输出：5 解释：选择下标 1 ，nums 变为 [4,-2,3] 。 复制代码
示例 2：
输入：nums = [3,-1,0,2], k = 3 输出：6 解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。 复制代码
示例 3：
输入：nums = [2,-3,-1,5,-4], k = 2 输出：13 解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。 复制代码
提示：
- 1 <= nums.length <= 10^41<=nums.length<=104
- -100 <= nums[i] <= 100−100<=nums[i]<=100
- 1 <= k <= 10^41<=k<=104
贪心 + 分情况讨论 + 模拟
假设取反前的总和为 sumsum，取反一个任意值 xx 后，对 sumsum 的影响为 - 2 * x−2∗x。
即取反一个负数会使得结果变大，取反正数会使结果变小，取反 00 值对结果没有影响。
因此，为了让取反后的结果尽可能的大，我们应当取反 -2*x−2∗x 尽可能大的数值。即按照「负数从小到大的顺序进行取反」。
对取反次数 kk 和 负数个数 cntcnt 进行分情况讨论：
- k <= cntk<=cnt：按照负数从小到大的顺序进行取反即可；
- k > cntk>cnt：按照负数从小到大的顺序进行取反后，根据「是否存在00值」和「剩余取反次数的奇偶性」进行分情况讨论：
- 存在 00 值 或 剩余取反次数为偶数：直接返回当前取反数组的总和（ 00 值可抵消任意次数的取反操作，将偶数次的取反操作应用在同一数值上，结果不变）；
- 不存在 00 值且剩余取反次数为奇数：此时从当前数值中取一个绝对值最小值（使用 idxidx 记录该值下标）进行取反，得到最终的取反数组。
最后对取反数组进行求和操作即可。
代码：
class Solution { public int largestSumAfterKNegations(int[] nums, int k) { int n = nums.length, idx = 0; PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->nums[a]-nums[b]); boolean zero = false; for (int i = 0; i < n; i++) { if (nums[i] < 0) q.add(i); if (nums[i] == 0) zero = true; if (Math.abs(nums[i]) < Math.abs(nums[idx])) idx = i; } if (k <= q.size()) { while (k-- > 0) nums[q.peek()] = -nums[q.poll()]; } else { while (!q.isEmpty() && k-- > 0) nums[q.peek()] = -nums[q.poll()]; if (!zero && k % 2 != 0) nums[idx] = -nums[idx]; } int ans = 0; for (int i : nums) ans += i; return ans; } } 复制代码
- 时间复杂度：对 numsnums 进行遍历，得到 idxidx 以及优先队列的复杂度为 O(n\log{n})O(nlogn)；从优先队列中取出元素进行取反操作的复杂度为 O(k\log{n})O(klogn)；对取反数组进行求和复杂度为 O(n)O(n)。整体复杂度为 O(n\log{n})O(nlogn)
- 空间复杂度：O(n)O(n)
优化优先队列
由于 numsnums 长度范围为 1000010000，但值域范围在 [-100, 100][−100,100]，因此我们可以使用计数数组 cntcnt 来替代优先队列的作用。
注意由于 nums[i]nums[i] 存在负数，因此需要增 100100 的偏移量。同时对于翻转操作，仅需要修改相应计数即可。
代码：
class Solution { public int largestSumAfterKNegations(int[] nums, int k) { int[] cnts = new int[210]; for (int i : nums) cnts[i + 100]++; for (int i = -100; i < 0 && k > 0; i++) { while (cnts[i + 100] != 0 && k-- > 0) { cnts[i + 100]--; cnts[-i + 100]++; } } if (cnts[0 + 100] == 0 && k > 0 && k % 2 != 0) { int val = 1; while (cnts[val + 100] == 0) val++; cnts[val + 100]--; cnts[-val + 100]++; } int ans = 0; for (int i = -100; i <= 100; i++) ans += i * cnts[i + 100]; return ans; } } 复制代码
- 时间复杂度：需要对 numsnums 以及大小为 C = 210C=210 的计数数组进行常数次扫描，复杂度为 O(n + C)O(n+C)
- 空间复杂度：O(C)O(C)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1005 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
