[leetcode6017]向数组中追加 K 个整数

发布于 2022-03-07  2265 次阅读


https://leetcode-cn.com/problems/append-k-integers-with-minimal-sum/

挺麻烦的题 给一个无序数组 要求插入k个正整数 这k个整数不能和数组中的数重复 求这k个数的和最小

显然 从1开始插是显而易见的办法

第一次方法 模拟直接开算 先用set存一下数 方便查找里面有没有出现过某个数 之后直接从1开始累加 遇到有的多加一个 结果TLE 明显想多了 k太大就会炸

正解:set存数完成去重加排序 之后对新的vector进行遍历 如果这个数小于k k++并且记录下这个数 直到处理完毕 直接用求根公式算出结果即可

#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;
  }
};

愿风指引你的道路,愿你的刀刃永远锋利。