leetcode刷题

1. 这道题采用桶排序，先用unordered_map来记录每个数字出现的频次。unordered_map就是python中的字典

unordered_mapcounts;		
    int max_count = 0;
	for (const int& num : nums) {
		max_count = max(max_count, ++counts[num]);
	}

2. 然后对桶的频次进行排序，这时候可以用一个二维矩阵来存，不过这个矩阵其实就是一个篮子。
   这里以后有时间再去看一下unordered_map和篮子在C++中的底层原理。
   比如buckets[5]存着[3,4,6]，整个数组中出现5次的数为[3,4,6]。然后我们根据对频次排序的结果就可以得知前k个频次最大的数是哪几个了。

class Solution {
public:
	vectortopKFrequent(vector& nums, int k) {
		unordered_mapcounts;		
        int max_count = 0;
		for (const int& num : nums) {
			max_count = max(max_count, ++counts[num]);
		}

		vector >buckets(max_count + 1);
		for (const auto& p : counts) {
			buckets[p.second].push_back(p.first);
		}

		vector ans;
		for (int i = max_count; i >= 0 && ans.size() < k; --i) {
			for (const int& num : buckets[i]) {
				ans.push_back(num);
				if (ans.size() == k) {
					break;
				}
			}
		}
		return ans;

	}
};

1. 这道题运用了桶排序的方法

class Solution {
public:
	string frequencySort(string s) {
		unordered_map counts;
		int max_count = 0;
		for (auto& str : s)
			max_count = max(max_count,++counts[str]);

		vector > buckets(max_count + 1);
		for (auto& p : counts) 
			buckets[p.second].push_back(p.first);

		string ans;
		for (int i = max_count; i >= 0; --i) {
			for (auto& str : buckets[i]) {
				for (int j = 0; j < i; j++)
					ans.push_back(str);
			}
		}
		return ans;
	}
};

2. 贴一个看到的题解简单写法，因为创建了unorded_map之后就可以直接对string使用sort排序了。

class Solution {
public:
    string frequencySort(string s) {
        unordered_map mp;
        for(auto ch:s) mp[ch]++;
        sort(s.begin(),s.end(),[&](const char &a, const char &b){
            return mp[a]==mp[b] ? a>b : mp[a]>mp[b];
        });
        return s;
    }
};

class Solution {
public:
    void sortColors(vector& nums) {
        map counts;
        for(auto& num : nums)
            ++counts[num];
        nums.clear();
        for (auto iter = counts.begin(); iter != counts.end();++iter)
            nums.insert(nums.end(), iter->second, iter->first);
    }
};