桶排序 TOPK

347. 前 K 个高频元素

给定一个非空的整数数组,返回其中出现频率前 k 高的元素。

示例 1:

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

输入: nums = [1], k = 1
输出: [1]
说明:

你可以假设给定的 k 总是合理的,且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
public class Threehundred_fortySeven {
    /**
     * 桶排序
     * 出现频率为frequency的元素放到下标为frequency的桶中
     * 时间复杂度为O(n)
     */
    public List<Integer> topKFrequent(int[] nums, int k) {
        if (nums == null || nums.length == 0)
            return new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums)
            map.put(num, map.getOrDefault(num, 0) + 1);
        List<Integer>[] bucket = new ArrayList[nums.length + 1];
        for (int key : map.keySet()) {//出现频率为frequency的元素放到下标为frequency的桶中
            int frequency = map.get(key);
            if (bucket[frequency] == null)
                bucket[frequency] = new ArrayList<>();
            bucket[frequency].add(key);
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = nums.length; i > 0 && ans.size() < k; i--) {
            if (bucket[i] == null)
                continue;
            if (bucket[i].size() <= (k - ans.size()))
                ans.addAll(bucket[i]);
            else
                ans.addAll(bucket[i].subList(0, k - ans.size()));
        }
        return ans;
    }
}
public List<Integer> topKFrequent2(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0 || k > nums.length)
            return new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        List<Integer> ans = new ArrayList<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return map.get(o1) - map.get(o2);//按出现次数排序的小根堆
            }
        });
        for (int key : map.keySet()) {
            pq.add(key);
            if (pq.size() > k)
                pq.poll();
        }
        while (!pq.isEmpty()) {
            ans.add(pq.poll());
        }
        Collections.reverse(ans);
        return ans;
    }
class Solution {
public:
    vector<int> topKFrequent(vector<int> &nums, int k) {
        map<int, int> count_map;
        for (auto num:nums) {
            count_map[num]++;//只有这样才会覆盖相同的key,make_pair不会检测重复的key
        }

        vector<int> bucket[nums.size() + 1];
        for (map<int, int>::iterator iter = count_map.begin(); iter != count_map.end(); iter++) {
            cout << iter->first << ":" << iter->second << endl;
            bucket[iter->second].push_back(iter->first);
        }
        vector<int> ans;
        for (int i = nums.size(); i > 0 && ans.size() < k; i--) {
            if (bucket[i].size() == 0)
                continue;
            if (bucket[i].size() <= (k - ans.size()))
                ans.insert(ans.end(), bucket[i].begin(), bucket[i].end());
            else
                ans.insert(ans.end(), bucket[i].begin(), bucket[i].begin() + k - ans.size());
        }
        return ans;
    }

    vector<int> topKFrequent2(vector<int> &nums, int k) {
        vector<int> ret;
        unordered_map<int, int> mp;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        for (auto i : nums) mp[i]++;
        for (auto p : mp) {
            pq.push(make_pair(p.second, p.first));
            if (pq.size() > k) pq.pop();
        }
        while (!pq.empty()) {
            ret.push_back(pq.top().second);
            pq.pop();
        }
        return ret;
    }
};

451. 根据字符出现频率排序

给定一个字符串,请将字符串里的字符按照出现的频率降序排列。

示例 1:

输入:
"tree"

输出:
"eert"

解释:
'e'出现两次,'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外,"eetr"也是一个有效的答案。
示例 2:

输入:
"cccaaa"

输出:
"cccaaa"

解释:
'c'和'a'都出现三次。此外,"aaaccc"也是有效的答案。
注意"cacaca"是不正确的,因为相同的字母必须放在一起。
示例 3:

输入:
"Aabb"

输出:
"bbAa"

解释:
此外,"bbaA"也是一个有效的答案,但"Aabb"是不正确的。
注意'A'和'a'被认为是两种不同的字符。
public class Fourhundred_fiftyOne {
    /**
     * 和343一致思路
     */
    public String frequencySort(String s) {
        Map<Character, Integer> frequencyForNum = new HashMap<>();
        for (char c : s.toCharArray())
            frequencyForNum.put(c, frequencyForNum.getOrDefault(c, 0) + 1);

        List<Character>[] frequencyBucket = new ArrayList[s.length() + 1];
        for (char c : frequencyForNum.keySet()) {
            int f = frequencyForNum.get(c);
            if (frequencyBucket[f] == null) {
                frequencyBucket[f] = new ArrayList<>();
            }
            frequencyBucket[f].add(c);
        }
        StringBuilder str = new StringBuilder();
        for (int i = frequencyBucket.length - 1; i >= 0; i--) {
            if (frequencyBucket[i] == null) {
                continue;
            }
            for (char c : frequencyBucket[i]) {
                for (int j = 0; j < i; j++) {
                    str.append(c);
                }
            }
        }
        return str.toString();
    }
}
public:
    string frequencySort(string s) {
        stringstream ans;
        unordered_map<char, int> mp;
        priority_queue<pair<int, char>, vector<pair<int, char>>, less<pair<int, char>>> pq;//大根堆
        for (auto c:s) {
            mp[c]++;
        }
        for (auto p:mp) {
            pq.push(make_pair(p.second, p.first));
        }
        while (!pq.empty()) {
            pair<int, char> ele = pq.top();
            for (int i = 0; i < ele.first; i++) {
                ans << ele.second;
            }
            pq.pop();
        }
        return ans.str();
    }
};

return the last

0

日常实习渠道

北京地区实习(按好用性排序):

    1. 北大未名(北大BBS):https://bbs.pku.edu.cn/v2/thread.php?bid=896&mode=topic
    2. 水木社区(清华BBS):http://www.newsmth.net/nForum/#!board/Intern
    3. 应届生(北京地区):http://www.yingjiesheng.com/beijing/ptjob.html
    4. 北邮人论坛(北邮BBS,目前外网进不去):https://bbs.byr.cn/#!board/jobinfo

上海地区实习(按好用性排序):

    1. 交大BBS(偏金融类):http://bbs.stmit.com/cxz.asp?topage=1&bd=71
    2. 复旦BBS(偏文科类):http://fdubbs.com/forum.php?ForumID=21
    3. 应届生(上海地区):http://www.yingjiesheng.com/shanghai/ptjob.html

网站合集(按好用性排序):

    1. Boss直聘(App/小程序/官网)
    2. 实习僧(App/小程序/官网)
    3. 应届生:http://www.yingjiesheng.com/
    4. (Dead,之前最好用)职象社区(微信小程序):http://www.iicareer.com/

备注:北京地区大概率和清北竞争,而且可能要前往北京(一般会有住房补贴)。上海地区由于互联网较少,IT类日常实习较少。

3+