algorithm - 选择数组中最大票数的最快算法是什么？

Question

问题:

正在进行员工投票以选择下一位董事会成员:

• 一名员工只能通过选择一个人来投票给一个被提名人唯一的员工编号(其中员工编号是 >= 0 的整数)

• 投票存储在一个数组中

• 获得最多选票的人将被选为下一位
  董事会成员

选择董事会成员的最有效算法是什么？

子问题:如果我们知道候选人人数少于选民人数怎么办，是否有更高效的算法？

可能的解决方案？

在这种情况下使用哈希表是否有意义，因为每个被提名人​​都有一个唯一的 ID？

或者我们可以先对数组进行排序(假设数组最初未排序)，然后通过遍历数组并跟踪最大计数器来跟踪获胜者:

投票[id] = [1,1,1,2,2,3,3,3,3,4]

所以只需遍历整个数组，maxCount = 4 for voterID = 3

那么，3 是赢家？

Answer 1

经典空间与性能权衡。

哈希表遍历数据 (N)。排序 + 计数需要 (N logN + N)。