发表于 2024.12.29

• 排序题，考察点在于如何实现排序规则。首先使用字典（由于队伍最多为26个，可以使用列表模拟字典）统计每个队伍的得票情况，然后根据字典转换为列表，排序规则为：按照得票情况降序排列，如果得票情况相同，则按照队伍名称的字典序升序排列。最后将排序后的队伍名称连接起来即可。

  C++的实现比较复杂些，首先统计得票情况，然后使用lambda表达式实现排序规则，最后将排序后的队伍名称连接起来即可。为了方便得到队伍名称，可以在得票情况列表最后添加队伍编号。

  class Solution {
  public:
      string rankTeams(vector<string>& votes) {
          int n = votes[0].size();
          vector<vector<int>> infos(26, vector<int>(n + 1));
          // infos[i][j]表示队伍i在第j个位置的得票情况
          // infos[i][n]表示队伍i的编号
          for (int i = 0; i < 26; ++i) infos[i][n] = i;
  
          for (const auto &vote : votes) {
              for (int i = 0; i < n; ++i) {
                  ++infos[vote[i] - 'A'][i];
              }
          }
          // 排序规则：按照得票情况降序排列，如果得票情况相同，则按照队伍名称的字典序升序排列
          std::sort(
              infos.begin(), infos.end(),
              [n](const auto& item1, const auto& item2) {
                  for (int i = 0; i < n; ++i) { if (item1[i] > item2[i]) return true; else if (item1[i] < item2[i]) return false; }
                  return item1[n] < item2[n];
              }
          );
          // 将排序后的队伍名称连接起来
          std::string ans;
          for (int i = 0; i < n; ++i) {
              ans += ('A' + infos[i][n]);
          }
          return ans;
      }
  };

  Python可以使用defaultdict统计得票情况，然后转换为元组列表，排序规则为：按照得票情况降序排列，如果得票情况相同，则按照队伍名称的字典序升序排列。最后连接起来即可。

  class Solution:
      def rankTeams(self, votes: List[str]) -> str:
          n = len(votes[0])
          info_map = defaultdict(lambda: [0] * n)
          for vote in votes:
              for i in range(n):
                  c = info_map[vote[i]]
                  # 使用负数计数, 这样排序的时候, 会变成从大到小排了, 而且字母是顺着排的
                  c[i] -= 1
      
          return ''.join(ch for *_, ch in sorted((*info_map[ch], ch) for ch in info_map))

• LC 题目链接