@(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 <= 10001 <= votes[i].length <= 26-
votes[i].length == votes[j].length，即每份投票结果长度相等 -
votes[i][j]全是英文大写字母 -
votes[i]中所有字符都是唯一的 - 在
votes[0]中出现的所有字符，也会在其他vote[j]中出现，1 <= j < votes.length。
解题思路
解题的关键，首先要弄清楚排序规则，从题目中可得知如下几点：
- 在某个位置上，票数高者获胜。
- 如果打成平手，则继续考虑后面位置的票数情况。若最终还是平手，则按字母顺序排。
但有个比较隐藏的规则，就是：位置的优先级大于票数。
举个栗子：
假设A 在位置 1 上有 1 票，B 在位置 2 上有 2 票，那么 A 会排在 B 前面。
这个规则，我一开始没有考虑到，怎么都对不上结果，通过查看多个栗子的结果才发现😆。
所以综合下来考虑，整体的排序规则为：
- 在同一位置，考虑票数。
- 若打成平手，继续考虑后面位置。若最终还是平手，则按字母顺序排序。
- 在不同位置，只需考虑位置情况。位置越靠前，则排名越靠前。
我的解法
解这个题，真是绕了好大一个圈。
刚开始想到的解法是：在每个位置上加上权重来计算团队的票数总和。因为位置越靠前，排名也靠前。
不知道为啥，直觉的想到以 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
}))
