正文索引 [隐藏]

传送门

T1一位数组的动态和

维护一个nums数组的前缀和，直接写。

class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        vector<int> pre;
        int n = nums.size();

        pre.push_back(nums[0]);
        for(int i = 1; i < n; i++)
        {
            int tmp = pre[i-1] + nums[i];
            pre.push_back(tmp);
        }

        return pre;
    }
};

T2不同整数的最小数目

题意很直观：给出一组整数arr与一个整数k，要求删除k个元素并使剩下的元素尽可能地少。

思路也很清晰，其实就是一个贪心策略。统计每个元素出现的次数，优先从出现次数少的开始删，最后剩下的元素个数就是答案。

考虑到数组中的元素范围是[0,1e9]，所以用hash表来离散处理。将统计用的hash表以出现次数为关键字做排序然后从头开始删就可以了。

bool cmp(const pair<int, int>& l, const pair<int, int>& r)
{
    return l.second > r.second;
}

class Solution {
public:
    int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
        map<int,int> num_map;
        int n = arr.size();

        for(int i = 0; i < n; i++)
            num_map[arr[i]]++;

        vector<pair<int, int>> num_vec(num_map.begin(), num_map.end());
        sort(num_vec.begin(), num_vec.end(), cmp);

        while(k--)
        {
            auto iter = num_vec.rbegin();
            iter->second--;
            if(iter->second == 0)
                num_vec.pop_back();
        }
        return num_vec.size();
    }
};