LeetCode 1366. Rank Teams by Vot

@(LeetCode)

问题描述

在一个特定的排序系统中，每个投票者为所有参赛的团队给出一个从高到低的排名。

团队的排序按照某个位置上票数最高的来计算，即票高者获胜。如果两个或者多个团队在第一的位置打成平手，那么考虑第二位置的票数，如果还是平手，那么继续考虑下一个位置，直至能区分胜负。如果在考虑到所有位置后，还是平手，那么就按照团队的字母顺序排序。

给定一个投票的字符串数组，按照上面的规则进行排序，返回由所有团队组成的字符串。

栗 1：

输入：votes = ["ABC","ACB","ABC","ACB","ACB"]
输出："ACB"

解释：
第一个位置：A 有 5 票，A:5
第二个位置：B 有 2 票，B:2；C 有 3 票，C:3。
第三个位置：C 有 2 票，C:2；B 有 3 票，B:3。

因此第一个位置为 A，第二个位置为 C，第三个位置为 B，即 "ACB"。

栗 2：

输入：votes = ["WXYZ","XYZW"]
输出："XWYZ"

解释：
第一个位置：W:1, X:1
第二个位置：X:1, Y:1
第三个位置：Y:1, Z:1
第四个位置：Z:1, W:1

在位置 1 上，W 和 X 打成平手，考虑位置 2。X 有 1 票，因此 X 是第一名，W 是第二名。
位置 2 上有 Y，而 Z 在位置 3 上，因此 Y 是第三名，Z 是第四名。最终结果为："XWYZ"。

栗 3：

输入：votes = ["ZMNAGUEDSJYLBOPHRQICWFXTVK"]
输出："ZMNAGUEDSJYLBOPHRQICWFXTVK"

解释：
因为只有一个人投票，所以结果就是其投票结果。

栗 4：

输入：votes = ["BCA","CAB","CBA","ABC","ACB","BAC"]
输出："ABC"

解释：
位置 1：A:2, B:2, C:2
位置 2：A:2, B:2, C:2
位置 3：A:2, B:2, C:2

由于 A/B/C 在位置 1 上是平手，则考虑位置 2。而在位置 2 上，也是平手，考虑位置 3。而位置 3 上也是平手，那么按字母顺序排序。
因此结果为 "ABC"。

栗 5：

输入：votes = ["M","M","M","M"]
输出："M"

解释：
因为只有一个队，所以第一名就是它自己。

注意：

• 1 <= votes.length <= 1000
• 1 <= votes[i].length <= 26
• votes[i].length == votes[j].length，即每份投票结果长度相等
• votes[i][j] 全是英文大写字母
• votes[i] 中所有字符都是唯一的
• 在 votes[0] 中出现的所有字符，也会在其他 vote[j] 中出现，1 <= j < votes.length。

想看英文原文的戳这里。

解题思路

解题的关键，首先要弄清楚排序规则，从题目中可得知如下几点：

1. 在某个位置上，票数高者获胜。
2. 如果打成平手，则继续考虑后面位置的票数情况。若最终还是平手，则按字母顺序排。

但有个比较隐藏的规则，就是：位置的优先级大于票数。

举个栗子：
假设A 在位置 1 上有 1 票，B 在位置 2 上有 2 票，那么 A 会排在 B 前面。

这个规则，我一开始没有考虑到，怎么都对不上结果，通过查看多个栗子的结果才发现😆。

所以综合下来考虑，整体的排序规则为：

1. 在同一位置，考虑票数。
2. 若打成平手，继续考虑后面位置。若最终还是平手，则按字母顺序排序。
3. 在不同位置，只需考虑位置情况。位置越靠前，则排名越靠前。

我的解法

解这个题，真是绕了好大一个圈。

刚开始想到的解法是：在每个位置上加上权重来计算团队的票数总和。因为位置越靠前，排名也靠前。

不知道为啥，直觉的想到以 2 来作为权重系数，即 2 ^ (len - i - 1)，len 为投票结果长度，i 为第几个位置。

举个栗子：
假设某个排名为 ABCD，那么 A 的结果为 2^3 = 8，B 的结果为 2^2 = 4，C 的结果为 2^1 = 2，D 的结果为 2^0 = 1。

依次计算所有排名，结果进行累加，则得出每个团队的票数总和。再按照大小进行排序，如果相等，则按照字母排序。

试了几个栗子，发现一个严重的问题，有可能排名靠前的团队计算出的票数 小于排名靠后的。因为如果靠后的团队票数较多，那么计算出来的结果很有很能大于前面的团队。

比如 ABC，CBA，CBA，CBA，这样计算出的总票数为如下：

A：4+1+1+1=7
B：2+2+2+2=8
C：1+4+4+4=13

而排序后的结果变成：CBA。正确结果应该为：ABC，o(╥﹏╥)o。

当时以为这个解法是错误的，遂放弃。（但是最终还是使用的这个解法，只不过调整了权重系数）

后来，又想了一些其他的方法。比如单独统计出每个位置上票数情况，然后按票数大小排序，对于票数相同的队，提取出来，往后做比较。

看起来想法没啥问题，但是实现上超级复杂，直到我不知该如下继续写下去了。花了好几个小时，未果。

但又转念想想，这个题目应该不至于这么复杂，因为它还是有 50.6% 的成功率。

最后想着想着，还是觉得初始的想法靠谱，需要解决的就是权重问题。而题目中说投票者的个数 <= 1000，那么只要保证计算出的结果不会有冲突就好。

我们考虑一下最极端的情况：假设投票者个数为 1000，团队分别为 A/B/C，位置 2 上团队 A 只有 1 票，位置 3 上团队 B 有 1000 票。

由于位置 3 是最后一个位置，那么该位置的权重为 1，B 计算出的总结果为 1000。
而 A 排在 B 前面，计算出的结果肯定要 > 1000 才行，反向推导出位置 2 的权重至少为 1001。

因此将权重从低位到高位，不断乘以 1001，可满足题目条件。即最后一位权重为 1，倒数第二位 1001，倒数第三位 1001 * 1001，...，第一位 1001 * 25。

下面给出计算部分关键代码：

// 记录各个球队得分情况, {{A: 100, B: 20}}
let map = new Map()

// 分别处理每列
while (i < len) {

  let j = 0

  while (j < votes.length) {
    const vote = votes[j]
    const ch = vote[i]

    let value = 0

    // 记录分数
    if (map.has(ch)) {
      value = map.get(ch)
    }

    // 乘以权重
    value += Math.pow(1001, (26 - i - 1))
    map.set(ch, value)

    j += 1
  }

  i += 1
}

排序部分，先按照票数排序，如果票数相等，再按字母排序。

const sortedMap = new Map([...map].sort((a, b) => {
  // 先按票数排序
  if (a[1] > b[1]) {
    return -1
  } else if (a[1] < b[1]) {
    return 1
  }

  // 按字顺序排序
  if (a[0] < b[0]) {
    return -1
  } else if (a[0] > b[0]) {
    return 1
  }

  return 0
}))

完整代码可点此查看。

正道解法

以上我的解法只能算是野路子，算一种奇淫技巧。看了讨论区的答案，才见识正道解法。

因为团队数最多只有 26 个，且为 A-Z，因此排名的位置至多为 26 个。只需统计出每个团队在每个位置上的票数情况，然后再排序。

举个栗子，假设 votes = ["BCA", "CAB", "CBA", "ABC", "ACB", "BAC"]。

计算出的结果为：

{ 'B' => [ 2, 2, 2 ], 'C' => [ 2, 2, 2 ], 'A' => [ 2, 2, 2 ]}

将 map 按照自定义的比较算法进行排序。value 是一个数组，逐个按位置对比数组中的元素值。若相同，继续往后比较，若不同，则返回较大的值。

排序关键代码如下：

// 排序
const sortedMap = new Map([...map].sort((a, b) => {
  // 逐个比较 b 中每个位置上得分
  const list1 = a[1]
  const list2 = b[1]

  let i = 0
  while (i < len) {
    // 按分数大小排
    if (list1[i] != list2[i]) {
      if (list1[i] > list2[i]) {
        return -1
      } else {
        return 1
      }
    }

    i += 1
  }

  // 按字顺序排序
  if (a[0] < b[0]) {
    return -1
  } else if (a[0] > b[0]) {
    return 1
  }
  return 0
}))

完整代码可点此查看。