通过投票对团队排名

通过投票对团队排名(medium)

做题过程

感觉又要用堆又要用哈希表的很麻烦，没想到简便思路。

算法概述

原题

本题要求为给出字符串数组用于表示投票结果，然后根据字符串中的名次以及该名次的出现次数决定最终结果。使用 哈希表 存储每个排名对象的名次。

• 时间复杂度为：填充哈希表的时间和排序（排序+比较）的时间
• 空间复杂度为

JAVA

class Solution {
    public String rankTeams(String[] votes) {
        int n = votes.length;
        // 初始化哈希
        Map<Character, int[]> ranking = new HashMap<>();
        // 用排名对象作为键
        for (char vid : votes[0].toCharArray()) {
            ranking.put(vid, new int[votes[0].length()]);
        }
        // 用数组（键值对的值）的下标表示排名，元素值表示该位次的出现频次
        for (String vote : votes) {
            for (int i = 0; i < vote.length(); ++i) {
                ++ranking.get(vote.charAt(i))[i];
            }
        }

        // 取出所有的键值对
        List<Map.Entry<Character, int[]>> result = new ArrayList<>(ranking.entrySet());
        // 排序
        result.sort((a, b) -> {
            for (int i = 0; i < a.getValue().length; i++) {
                // 一直找到不相等的位次，然后降序排列
                if (a.getValue()[i] != b.getValue()[i]) {
                    return b.getValue()[i] - a.getValue()[i];
                }
            }
            // 所有位次的结果都一样，就直接按照字母顺序排（升序）
            return a.getKey() - b.getKey();
        });

        StringBuilder ans = new StringBuilder();
        for (Map.Entry<Character, int[]> entry : result) {
            ans.append(entry.getKey());
        }
        return ans.toString();
    }
}

总结

主要是用到了一下几个数据结构，比较重要，组织好数据结构也需要深入思考：

• Map<Character, int[]> ranking = new HashMap<>();：用int[]作为值，我只想到了用整数以及哈希数组，这样就可以完整存储所有排序对象的排名结果了
• List<Map.Entry<Character, int[]>> result = new ArrayList<>(ranking.entrySet());：用List变长数组存储Map.Entry元素，而不是直接遍历，这样可以快速用数组的自定义排序器进行排序