目录
题目描述
1005. Maximize Sum Of Array After K Negations
三种方法都是贪心。
方法一、使用小根堆
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
int sum = std::accumulate(nums.begin(),nums.end(),0);
priority_queue<int,vector<int>,std::greater<int>> minHeap(nums.begin(),nums.end());
while(k--){
int min = minHeap.top();
minHeap.pop();
minHeap.push(-min);
sum -= (2*min);
}
return sum;
}
};还可以优化一下。处理完负数后，当剩余数字全部是非负数的时候，可以一次处理结束。
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
int sum = std::accumulate(nums.begin(),nums.end(),0);
priority_queue<int,vector<int>,std::greater<int>> minHeap(nums.begin(),nums.end());
while(k){
int min = minHeap.top();
if(min>=0){
if(k%2==1)
sum -=(2*min);
break;
}
minHeap.pop();
minHeap.push(-min);
sum -= (2*min);
k--;
}
return sum;
}
};方法二、排序
按照绝对值从大到小排序。
class Solution {
struct Cmp{
bool operator()(int a,int b) const{
return abs(a)>abs(b);
}
};
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(),nums.end(),Cmp());
int n = nums.size();
for(int i = 0;i < n;i++){
if(k>0 && nums[i] < 0){
nums[i]*=-1;
k--;
}
if(k ==0)
break;
}
if(k%2==1) nums[n-1]*=-1;
return accumulate(nums.begin(),nums.end(),0);
}
};方法三、哈希
由于-100 <= nums[i] <= 100，故方法二的排序可以用哈希替代。
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
int sum = 0;
unordered_map<int,int> count;
for(int num:nums){
count[num]++;
sum += num;
}
for(int i = -100;i <0;i++){
if(count[i] > 0){
int operation_cnt = min(count[i],k);
sum -= operation_cnt*2*i;
k -= operation_cnt;
count[i] -= operation_cnt;
count[-i]+= operation_cnt;
if(k == 0)
break;
}
}
if(k>0 && k%2==1 && count[0]==0){
for(int i = 0;i <=100;i++){
if(count[i]>0){
sum -= 2*i;
break;
}
}
}
return sum;
}
};