C语言重构【1005】 K 次取反后最大化的数组和

电玩女神 2022-12-21 14:55 175阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。）
    
    以这种方式修改数组后，返回数组可能的最大和。
    
     
    
    示例 1：
    
    输入：A = [4,2,3], K = 1
    输出：5
    解释：选择索引 (1,) ，然后 A 变为 [4,-2,3]。
    示例 2：
    
    输入：A = [3,-1,0,2], K = 3
    输出：6
    解释：选择索引 (1, 2, 2) ，然后 A 变为 [3,1,0,2]。
    示例 3：
    
    输入：A = [2,-3,-1,5,-4], K = 2
    输出：13
    解释：选择索引 (1, 4) ，然后 A 变为 [2,3,-1,5,4]。
     
    
    提示：
    
    1 <= A.length <= 10000
    1 <= K <= 10000
    -100 <= A[i] <= 100

#### 方案： ####

*  利用数组来比年每次寻找最小值的麻烦

class Solution
    { 
    public:
        int largestSumAfterKNegations(vector<int> &A, int K)
        { 
            vector<int> nums(201, 0);
            for (int i = 0; i < A.size(); i++)
            { 
                nums[A[i] + 100]++;
            }
            int index = 0;
            while (K-- > 0)
            { 
                // 找到第一个不为0的数
                while (nums[index] == 0)
                    index++;
                nums[index]--;
                nums[200 - index]++;
                if (index > 100)
                { 
                    K = K % 2;           //降低循环次数
                    index = 200 - index; //降低寻找次数
                }
            }
            int sum = 0;
            for (int i = 0; i < 201; i++)
            { 
                if (nums[i] != 0)
                    sum += nums[i] * (i - 100);
            }
            return sum;
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(1) ；<=201

[Git]: https://github.com/ch98road/leetcode