1366 通过投票对团队排名

· 2024-12-29   · 次阅读   · 字数统计: 197字   · 阅读时长≈ 1分钟

  · 算法题解   · LeetCode

题目链接

1366. 通过投票对团队排名

分析

自定义排序

用一个数组 $cnt[i][j]$ 记录队伍 $i$ 在第 $j$ 个排位的票数，用该数组对队伍进行自定义排序即可

注意此处排序为按照字典序排序

代码实现

class Solution {
public:
    string rankTeams(vector<string>& votes) {
        int m = votes[0].length();
        vector<vector<int>> cnt(26, vector<int>(m));
        for(string vote : votes) {
            for (int i = 0; i < m; ++i) {
                cnt[vote[i] - 'A'][i]++;
            }
        }

        ranges::sort(votes[0], ranges::greater{}, [&](char c) { return make_pair(cnt[c - 'A'], -c); });
        return votes[0];
    }
};

复杂度分析

  • 时间复杂度：$O(nm + m^2 \log m)$，其中 $n$ 为 $votes$ 的长度， $m$ 为 $votes[i]$ 的长度
  • 空间复杂度：$O(m^2)$