特殊排名系统

根据参赛团队在投票人心中的次序进行排名，每个投票者都需要按从高到低的顺序对参与排名的所有团队进行排位。

排名规则

1. 参赛团队的排名次序依照其所获「排位第一」的票的多少决定。
2. 若存在多个团队并列，则继续考虑其「排位第二」的票的数量。以此类推，直到不再存在并列的情况。
3. 若考虑完所有投票情况后仍然并列，则根据团队字母的字母顺序进行排名。

给定一个字符串数组 votes 代表全体投票者的排位情况，请根据上述规则对所有参赛团队进行排名，返回表示排序后结果的字符串。

---

示例

示例 1

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

输出
"ACB"

解释

• A 队获得五票「排位第一」，排名第一
• B 队：2 票「排位第二」，3 票「排位第三」
• C 队：3 票「排位第二」，2 票「排位第三」
• C 队因「排位第二」票数更多，排名第二，B 队第三

示例 2

输入
votes = ["WXYZ","XYZW"]

输出
"XWYZ"

解释

• X 队和 W 队「排位第一」票数相同，但 X 队有 1 票「排位第二」，打破僵局

示例 3

输入
votes = ["ZMNAGUEDSJYLBOPHRQICWFXTVK"]

输出
"ZMNAGUEDSJYLBOPHRQICWFXTVK"

解释

• 仅一个投票者，排名完全按投票意愿

---

提示

• 1 <= votes.length <= 1000
• 1 <= votes[i].length <= 26
• votes[i].length == votes[j].length（对所有 0 <= i, j < votes.length 成立）
• votes[i][j] 为大写英文字母
• votes[i] 中的所有字母唯一
• votes[0] 中包含的字母会出现在所有 votes[j] 中（1 <= j < votes.length）

代码分析

---

1. 类的定义与封装

• 类的结构：
  定义 team 类，包含成员变量 votes（存储各排位得票数）和 name（团队名称），通过构造函数初始化属性。

  class team {
    var votes: Array<Int64>
    var name: Rune
    init(name: Rune, size: Int64) {
      this.name = name
      votes = Array<Int64>(size, item: 0) // 初始化投票数组
    }
    // 方法定义...
  }
  

• 方法的封装：
  通过 addVotes 增加票数，getVotes 和 getName 提供数据访问，符合面向对象封装原则。

---

2. 集合类型的使用

• 哈希表存储对象：
  使用 HashMap<Rune, team> 以团队名称为键，快速查找团队对象。

  var teams: HashMap<Rune, team> = HashMap<Rune, team>()
  teams.put(name, team(name, teamsSize)) // 存储对象
  

• 动态数组操作：
  用 ArrayList<team> 存储待排序的团队列表，支持动态追加元素。

  teamArr.append(teams[name])
  

---

3. 排序算法的实现

• 自定义比较函数：
  通过 sortBy 方法实现多级排序：

  1. 优先级排序：从高到低比较各排位得票数。
  2. 字母序保底：若所有排位票数相同，按名称字母序升序排列。

  teamArr.sortBy(stable: true) { rht: team, lht: team =>
    for (i in 0..teamsSize) {
      if (rht.getVotes(i) < lht.getVotes(i)) return Ordering.GT // 降序排列
      else if (rht.getVotes(i) > lht.getVotes(i)) return Ordering.LT
    }
    // 按字母序升序排列
    if (rht.getName() < lht.getName()) return Ordering.LT else return Ordering.GT
  }
  

• 稳定排序：
  通过 stable: true 确保等价元素的原始顺序保留（尽管此处逻辑已完全覆盖所有比较条件）。

---

4. 循环与条件控制

• 遍历投票数据：
  双层循环遍历所有投票的每个排位，统计得票数。

  for (i in 1..votes.size) {
    for (j in 0..teamsSize) {
      teams[Rune(votes[i][j])].addVotes(j) // 统计各排位票数
    }
  }
  

• 边界处理：
  循环范围 0..teamsSize

---

5. 字符串与字符处理

• 字符提取：
  使用 Rune 类型处理字符串中的单个字符，作为团队唯一标识。

  let name = Rune(votes[0][i]) // 从字符串中提取字符
  

---

时间复杂度与空间复杂度分析

时间复杂度

1. 初始化阶段

   • 遍历首个投票字符串构建 team 对象：O(M)（M为团队数量）
   • 遍历所有投票统计各排位票数：O(N*M)（N为投票数）
   • 排序操作：O(M^2 log M)（每次比较需遍历 M 个排位，总排序复杂度为 M^2 log M）

   总时间复杂度：O(N*M + M^2 log M)

2. 空间复杂度

   • 每个 team 对象存储长度为 M 的票数数组：O(M^2)
   • 哈希表与动态数组存储团队对象：O(M)

   总空间复杂度：O(M^2)

---

优化空间

应该可以把得票优化为0x3FF => 1023 => 10bit 的参数（最多1000个votes），如有3个队伍参与就是3x10bit？maybe，但是感觉逻辑蛮复杂的

---

踩坑：
1、hashMap没有实现sortBy，比起实现还是挪到ArrayList进行排序好，hashMap相关逻辑也可以用ArrayList打包元组类型
let teamItem: (Rune, team) = (name, team(name, size)但是反正hashMap的逻辑也写了，懒得改了，顺便强化下hashMap的操作印象

---

源码：

class team{
    var votes:Array<Int64> 
    var name : Rune
    init(name:Rune, size:Int64){
        this.name = name
        votes = Array<Int64>(size, item:0)
    }
    func addVotes(order:Int64){
        votes[order]++
    }
    func getVotes(order:Int64){
        return votes[order]
    }
    func getName(){
        return this.name
    }
}

class Solution {
    func rankTeams(votes: Array<String>): String {
        let teamsSize = votes[0].size
        var teams : HashMap<Rune, team> = HashMap<Rune, team>()
        var teamArr = ArrayList<team>()
        var res:String = ""

        for(i in 0..teamsSize){
            let name = Rune(votes[0][i])
            teams.put(name, team(name, teamsSize))
            teams[name].addVotes(i)
        }
        
        for(i in 1..votes.size){
            for(j in 0..teamsSize){
                teams[Rune(votes[i][j])].addVotes(j)
            }
        }

        for(k in 0..teamsSize){
            let name = Rune(votes[0][k])
            teamArr.append(teams[name])
        }

        teamArr.sortBy(stable:true){
            rht:team, lht:team =>
            for(i in 0..teamsSize){
                if(rht.getVotes(i) < lht.getVotes(i)){
                    return Ordering.GT
                } else if(rht.getVotes(i) > lht.getVotes(i)){
                    return Ordering.LT
                }
            }
            if(rht.getName() < lht.getName()){
                return Ordering.LT
            } else {
                return Ordering.GT
            }
        }

        for(k in 0..teamsSize){
            // print("""
            // name is ${teamArr[k].getName()}
            // votes is 
            // """)
            // for(i in 0..teamsSize){
            //     print("${teamArr[k].getVotes(i)} ")
            // }
            // println()
            res += "${teamArr[k].getName()}"
        }
        
        return res
    }
}