1005. K 次取反后最大化的数组和

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

贪心+哈希表

利用题目条件，遍历负数范围而不是数组元素。逆向思维。

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

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        // 创建一个哈希表，用于记录每个数字出现的频率
        Map<Integer, Integer> freq = new HashMap<>();
        // 遍历数组 nums，统计每个数字出现的频率。重点。
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        
        // 计算数组 nums 的初始总和
        int ans = Arrays.stream(nums).sum();
        
        // 重点，遍历容量。尝试从 -100 到 -1 的数字进行翻转。题目说nums[i]的取值范围是[-100,100]
        for (int i = -100; i < 0; ++i) {
            // 如果哈希表中包含当前数字 i。遍历物品。
            if (freq.containsKey(i)) {
                // 计算能够翻转的次数 ops，即取 k 和当前数字频率的较小值。重点。贪心策略。
                int ops = Math.min(k, freq.get(i));
                
                // 更新总和 ans，翻转 ops 次 i，相当于增加 (-i) * ops * 2
                ans += (-i) * ops * 2;
                
                // 更新哈希表中当前数字 i 的频率
                freq.put(i, freq.get(i) - ops);
                // 更新哈希表中翻转后数字 -i 的频率。注意是getOrDefault
                freq.put(-i, freq.getOrDefault(-i, 0) + ops);
                
                // 减少 k 的值
                k -= ops;
                // 如果 k 为 0，结束循环
                if (k == 0) {
                    break;
                }
            }
        }
        
        // 如果 k 大于 0 （即k大于100，负数不够用，需要反转正数）并且 k 是奇数且没有 0 存在于哈希表中。重点。
        if (k > 0 && k % 2 == 1 && !freq.containsKey(0)) {
            // 从 1 到 100 的数字中找到最小的正数并翻转一次。因为没有0，所以只能从1开始
            for (int i = 1; i <= 100; ++i) {
                if (freq.containsKey(i)) {
                    ans -= i * 2;
                    break;
                }
            }
        }
        
        // 返回最终的总和
        return ans;
    }
}

• 时间复杂度： $O(n+C)$ ，其中 $n$ 是数组 nums 的长度， $C$ 是数组 nums 中元素的范围，本题中 $C=201$。我们需要 $O(n)$ 的时间使用桶或哈希表统计每个元素出现的次数，随后需要 $O(C)$ 的时间对元素进行操作。
• 空间复杂度： $O(C)$ ，即为桶或哈希表需要使用的空间。