【LeetCode每日一题】【2021/12/3】1005. K 次取反后最大化的数组和

文章目录


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

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

简 单 \color{#00AF9B}{简单} 简单

给你一个整数数组 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

方法1:贪心 + 排序

对于数组中所有已存的负数,可以进行至多k次的取反,每次取反要尽量选择更小的负数(贪心)。这样剩余的大的负数对最大和的负面影响更小;而值小的负数取反后变为值大的正数,对最大和的正面影响最大。

  1. 如果坐满了k次操作,不管数组中是否还有负数,此时就已经是可能的最大和了。因为剩余的负数是对最大和负面影响最小的了。

  2. 若将所有负数都取反后,即此时数组中皆为正数,却还有剩余次数要做,设已经完成done次取反,则剩余的次数为k-done,此时一共分为2种情况:

    • 如果k-done为偶数。由于【可以对同一个数进行多次的取反】,我们可以将其中的偶数次全都抽象地附加于任意的同一数上。由于一个数取偶数次的反仍是它本身,这样一来数组仍为原数组。又因为此时数组中都是正数,所以此时是确定的最大和了。
    • 如果k-done为奇数。同理,将其中的偶数次附加于同一数上。这样一来就剩下了1次取反,我们当然希望是将最小的正数取反,这样对最大和的负面影响才最小。

为了更好的定位元素,我们可以先排序,排序时按照每个元素的绝对值从小到大进行。

#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
class Solution
{
public:
    int largestSumAfterKNegations(vector<int> &nums, int k)
    {
        const int n = nums.size();
        sort(nums.begin(), nums.end(), [](int &left, int &right)
             { return abs(left) < abs(right); });

        int done = 0;
        for (int i = n - 1; i >= 0; i--)
        {
            if (nums[i] < 0 && done < k)
            {
                nums[i] = -nums[i];
                done++;
                if (done == k)
                    break;
            }
        }
        if ((k - done) % 2 != 0)
        {
            for (int i = 0; i < n; i++)
            {
                if (nums[i] >= 0)
                {
                    nums[i] = -nums[i];
                    break;
                }
            }
        }
        return accumulate(nums.begin(), nums.end(), 0);
    }
};

复杂度分析

  • 时间复杂度: O ( n log ⁡ n ) O(n \log n) O(nlogn)。std::sort为快速排序,时间复杂度为 O ( n log ⁡ n ) O(n \log n) O(nlogn);数组中每个元素最多被遍历2此。因此时间复杂度为 O ( n log ⁡ n ) + O ( 2 n ) = O ( n log ⁡ n ) O(n \log n)+O(2n)=O(n \log n) O(nlogn)+O(2n)=O(nlogn)

  • 空间复杂度: O ( log ⁡ n ) O(\log n) O(logn)。主要为快速排序的递归消耗。

参考结果

Accepted
80/80 cases passed (4 ms)
Your runtime beats 89.82 % of cpp submissions
Your memory usage beats 55.63 % of cpp submissions (8.8 MB)

方法2:贪心 + 哈希表

题目中给出数组中元素的范围为:-100 <= nums[i] <= 100,可以发现一共只有201个数,数量级较小,所以我们对每个元素计数的话,哈希表的长度也只有201

我们假设有一个数轴,其范围为[-100, 100],而数轴上的元素代表着该数的计数。我们对每个数进行计数的话,对于每个负数,将其取反的操作就变成了:负数计数减1,相应的整数计数加1,最后求和时我们把每个计数不为0的数,将其下标和计数相乘即可加入和。

由于数轴本身就是从小到大排列的,因此我们的计数就隐含了从小到大的规律,因为计数值和它的下标时直接关联的。因此我们可以直接定位到最小的负数和最小的正数,这样就省去了排序的时间。


数组

我们可以定义一个长为201的数组,每一项的初值均为0。由于数组下标的起始为0,而本题中的数值到达-100,因此需要做一定的转换。设常熟pivot=100作为元素0的计数位置,这样[-100, -1]就对应着哈希表中的[0, 99],而[1, 100]就对应着哈希表中的[101, 200]。

#include <vector>
using namespace std;
class Solution
{
public:
    int largestSumAfterKNegations(vector<int> &nums, int k)
    {
        const int n = nums.size();
        int *cnts = new int[201]{};
        const int pivot = 100;

        for (const int num : nums)
        {
            cnts[num + pivot]++;
        }

        for (int i = -100; i < 0; i++)
        {
            if (cnts[i + pivot] != 0)
            {
                int ops = min(k, cnts[i + pivot]);
                cnts[i + pivot] -= ops;
                cnts[-i + pivot] += ops;
                k -= ops;
                if (k == 0)
                    break;
            }
        }
        if (k > 0 && k % 2 == 1 && cnts[pivot] == 0)
        {
            for (int i = 1; i <= 100; i++)
            {
                if (cnts[i + pivot] != 0)
                {
                    cnts[i + pivot]--;
                    cnts[-i + pivot]++;
                    break;
                }
            }
        }
        int ans = 0;
        for (int i = -100; i <= 100; i++)
        {
            if (cnts[i + pivot] != 0)
            {
                ans += i * cnts[i + pivot];
            }
        }
        return ans;
    }
};

std::unordered_map

我们也可以使用STL中的std::unordered_map来完成,这样就省去了用pivot重新定位的步骤。

#include <vector>
#include <unordered_map>
using namespace std;
class Solution
{
public:
    int largestSumAfterKNegations(vector<int> &nums, int k)
    {
        const int n = nums.size();
        unordered_map<int, int> cnts;

        for (const int num : nums)
        {
            cnts[num]++;
        }

        for (int i = -100; i < 0; i++)
        {
            if (cnts[i] != 0)
            {
                int ops = min(k, cnts[i]);
                cnts[i] -= ops;
                cnts[-i] += ops;
                k -= ops;
                if (k == 0)
                    break;
            }
        }
        if (k > 0 && k % 2 == 1 && cnts[0] == 0)
        {
            for (int i = 1; i <= 100; i++)
            {
                if (cnts[i] != 0)
                {
                    cnts[i]--;
                    cnts[-i]++;
                    break;
                }
            }
        }
        int ans = 0;
        for (int i = -100; i <= 100; i++)
        {
            if (cnts[i] != 0)
            {
                ans += i * cnts[i];
            }
        }
        return ans;
    }
};

复杂度分析

  • 时间复杂度: O ( n + C ) O(n+C) O(n+C)。其中,n是数组的长度,Cnums中元素的范围,在本题中C即为201。

  • 空间复杂度: O ( C ) O(C) O(C)。主要为哈希表的开销。

参考结果

Accepted
80/80 cases passed (8 ms)
Your runtime beats 44.56 % of cpp submissions
Your memory usage beats 5.17 % of cpp submissions (9.9 MB)
上一篇:Flume | 安装部署


下一篇:【SCC】Proving Equivalences UVALive - 4287