查找热点数据问题 | 数据结构

问题描述

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按任意顺序返回答案。

• 1 <= nums.length <= 10^5
• k 的取值范围是 [1, 数组中不相同的元素的个数]
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

你所设计算法的时间复杂度必须优于 O(n log n) ，其中 n 是数组大小。

示例 1

输入: nums = [1,1,1,2,2,3], k = 2

输出: [1,2]

示例 2

输入: nums = [1], k = 1

输出: [1]

题解：

        题目很简单，就是将数组中数的重复次数排序输出而已，所以只要用一个map来记录重复次数，然后将map的key和value交换一次，用一个新的map2来记录（map2要开int，vector<int>的，因为可能有重复的次数），因为map自带排序，所以用迭代器从后往前遍历即可，放进一个新的vector里，然后sort加处理就可以了。

        下面代码用的是set，这样可以把重复次数的数从小到大排序，但是没必要（没看题目是这样的）。

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<map>
#include<set>
using namespace std;
typedef long long int ll;

string solution(vector<int> nums, int k) {
    map<int ,int > mp1;
    for(int i=0;i<nums.size();i++){
        if(mp1.find(nums[i])==mp1.end()){
            mp1[nums[i]]=1;
        }
        else{
            mp1[nums[i]]++;
        }
    }
    map<int,int>::iterator it;
    /*
    for(it=mp1.begin();it!=mp1.end();it++){
        cout << it->first << " " << it->second << " ";
    }
    cout << "\n";
    */
    map<int,set<int>>::iterator it2;
    map<int,set<int>> mp2;
    for(it=mp1.begin();it!=mp1.end();it++){
        mp2[it->second].insert(it->first);
    }
    /*
    cout << "-------" << "\n";
    for(it2=mp2.begin();it2!=mp2.end();it2++){
        cout << it2->first << " ";
    }
    cout << "\n";
    cout << "-------" << "\n";
    */
    vector<int> vt;
    it2=mp2.end();
    it2--;
    set<int>::iterator it3;
    while(k>0){
        for(it3=it2->second.begin();it3!=it2->second.end();it3++){
            vt.push_back(*it3);
            k--;
            if(k==0){
                break;
            }
        }
        it2--;
    }
    sort(vt.begin(),vt.end());
    /*
    for(int i=0;i<vt.size();i++){
        cout << vt[i] << " ";
    }
    cout << "\n";
    */
    string a;
    for(int i=0;i<vt.size()-1;i++){
        a+=(char)(vt[i]+48);
        a+=',';
    }
    a+=(char)(vt[vt.size()-1]+48);
    return a;
}

int main() {
    //  You can add more test cases here
    std::vector<int> nums1 = {1, 1, 1, 2, 2, 3};
    std::vector<int> nums2 = {1};

    std::cout << (solution(nums1, 2) == "1,2") << std::endl;
    std::cout << (solution(nums2, 1) == "1") << std::endl;

    return 0;
}