https://leetcode-cn.com/problems/append-k-integers-with-minimal-sum/
挺麻烦的题 给一个无序数组 要求插入k个正整数 这k个整数不能和数组中的数重复 求这k个数的和最小
显然 从1开始插是显而易见的办法
第一次方法 模拟直接开算 先用set存一下数 方便查找里面有没有出现过某个数 之后直接从1开始累加 遇到有的多加一个 结果TLE 明显想多了 k太大就会炸
正解：set存数完成去重加排序 之后对新的vector进行遍历 如果这个数小于k k++并且记录下这个数 直到处理完毕 直接用求根公式算出结果即可
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
32
33
34
35
36
37
38
39
40
41
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
class Solution
{
public:
long long minimalKSum(vector<int> &nums, int k)
{
set<int> st;
for (const int &i : nums)
{
st.insert(i);
}
vector<int> arr;
//去重加排序
for (const int &i : st)
{
arr.push_back(i);
}
ll t = 0, kk = k;
//换一种思路 不是看范围内的这个数是不是在数组中 而是看数组中的这个数在不在范围内 大大减小枚举量
for (const int &i : arr)
{
if (i <= kk)
{
kk++;
t += i;
}
}
// k个数 检查一下前k个数里面 原数组有几个
// for(int i=1;i<=k;i++){
// if(st.count(i)){
// //如果存在这个数
// k++;
// t+=i;
// }
// }
return 1LL * (1 + kk) * kk / 2 - t;
}
};
|