1366. Rank Teams by Votes

题目详见:1366. Rank Teams by Votes

解法一

思路

这道题是非常 straightforwad 的题目,只要读懂题意,看懂几个例子代表的 edge case 就可以写出代码。

可以利用一个 HashMap 来记录每个字母的得票情况,统计完成后,将字母依次加入定义好的 PriorityQueue 中。我们需要预先重写 PriorityQueue 的排序方式。

最后将 PriorityQueue 中的字母按序取出拼接成字符串。

代码
class Solution {
    public String rankTeams(String[] votes) { 
        int length = votes[0].length(); // 字母个数
        Map<Character, int[]> map = new HashMap<>();

        // 对每次投票不同位置的字母依次取出
        for (String vote : votes) {
            for (int i = 0; i < length; i++) {
                char c = vote.charAt(i);
                map.putIfAbsent(c, new int[length]);
                map.get(c)[i]++; // 对该字母相应位次计数
            }
        }

        PriorityQueue<Character> pq = new PriorityQueue<>(new Comparator<Character>(){
        @Override
        public int compare(Character a, Character b) {
            int[] aRank = map.get(a);
            int[] bRank = map.get(b);

            for (int i = 0; i < length; i++) {
                if (aRank[i] != bRank[i]) {
                    return bRank[i] - aRank[i]; // 降序排列, 即得票权重高的在顶端
                }
            }
            return a - b; // 如果所有字母得票情况一样, 升序排列, 即按字母顺序排列            
        }
        });

        for (Map.Entry<Character, int[]> entry : map.entrySet()) {
            pq.offer(entry.getKey());
        }

        StringBuilder sb = new StringBuilder(); // Generate the result
        while (!pq.isEmpty()) {
            sb.append(pq.poll());
        }

        return sb.toString();
    }
}
复杂度分析
  • 时间复杂度 遍历数组 O(26N), 将数组添加进 PriorityQueue 需要 O(26N*logN) 的时间,所以总时间复杂度 O(NlogN).
  • 空间复杂度 最多有26个字母,votes 数组长度为 N,则 map 需要有 O(26N) = O(N) 的空间来储存
本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 2
class Solution {

    /**
     * @param String[] $votes
     * @return String
     */
    function rankTeams($votes) {
        if(strlen($votes[0]) == 1) return $votes[0]; 
        //所有参赛队伍
        $team = str_split($votes[0]);
        $voteCount = array();
        //初始化
        foreach ($team as $key => $value) {
            $voteCount[$value] = array();
            for ($i=0; $i < count($team); $i++) { 
                $voteCount[$value][$i+1] = 0;
            }
        }
        //得到投票结果
        for ($i=0; $i < count($votes); $i++) { 
            //每一个人的投票结果
            $str = $votes[$i];
            for ($j=0; $j <strlen($str); $j++) {
                $voteCount[$str[$j]][$j+1]++;
            }
        }

        ksort($voteCount);
        uasort($voteCount, array($this, 'cmp'));
        $result = implode('', array_keys($voteCount));
        return $result;
    }
    //自定义排序算法
    function cmp($a, $b){
        for ($i=1; $i <= count($a); $i++) { 
            if($a[$i] > $b[$i]) return -1;
            if($a[$i] == $b[$i]) continue;
            if($a[$i] < $b[$i]) return 1;
        }
    }
}

思路:

  1. 得到每个队伍排名一二三的数量
  2. 自定义排序算法
4年前 评论

思路差不多,我用 php 写的

4年前 评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!