问题描述

给你一个整数数组 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 <= 104
  • -100 <= nums[i] <= 100
  • 1 <= k <= 104

核心思路

核心思路

由于我们希望数组的和尽可能大，因此除非万不得已，我们应当总是修改负数，并且优先修改值最小的负数。因为将负数 −x−x 修改成 xx 会使得数组的和增加 2x2x，所以这样的贪心操作是最优的。

当给定的 KK 小于等于数组中负数的个数时，我们按照上述方法从小到大依次修改每一个负数即可。但如果 KK 的值较大，那么我们不得不去修改非负数（即正数或者 0）了。由于修改 0 对数组的和不会有影响，而修改正数会使得数组的和减小，因此：

  • 如果数组中存在 0，那么我们可以对它进行多次修改，直到把剩余的修改次数用完；

  • 如果数组中不存在 0 并且剩余的修改次数是偶数，由于对同一个数修改两次等价于不进行修改，因此我们也可以在不减小数组的和的前提下，把修改次数用完；

  • 如果数组中不存在 0 并且剩余的修改次数是奇数，那么我们必然需要使用单独的一次修改将一个正数变为负数（剩余的修改次数为偶数，就不会减小数组的和）。为了使得数组的和尽可能大，我们就选择那个最小的正数。

    需要注意的是，在之前将负数修改为正数的过程中，可能出现了（相较于原始数组中最小的正数）更小的正数，这一点不能忽略。

实现要点

为了实现上面的算法，我们可以对数组进行升序排序，首先依次遍历每一个负数（将负数修改为正数），再遍历所有的数（将 0 或最小的正数进行修改）。

然而注意到本题中数组元素的范围为 [-100, 100]，因此我们可以使用计数数组（桶）或者哈希表，直接统计每个元素出现的次数，再升序遍历元素的范围，这样就省去了排序需要的时间。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        for (int num: nums) {
            freq[num] += 1;
        }
        int ans = accumulate(nums.begin(), nums.end(), 0);
        for (int i = -100; i < 0; ++i) {
            if (freq[i]) {
                int ops = min(k, freq[i]);
                ans += (-i) * ops * 2;
                freq[i] -= ops;
                freq[-i] += ops;
                k -= ops;
                if (k == 0) {
                    break;
                }
            }
        }
        if (k > 0 && k % 2 == 1 && !freq[0]) {
            for (int i = 1; i <= 100; ++i) {
                if (freq[i]) {
                    ans -= i * 2;
                    break;
                }
            }
        }
        return ans;
    }
};

  • 时间复杂度：O(n+C)O(n + C)，其中 n 是数组 nums\textit{nums} 的长度，CC 是数组 nums\textit{nums} 中元素的范围，本题中 C=201C=201。

    我们需要 O(n)O(n) 的时间使用桶或哈希表统计每个元素出现的次数，随后需要 O(C)O(C) 的时间对元素进行操作。

  • 空间复杂度：O(C)O(C)，即为桶或哈希表需要使用的空间。