Elections Winners

"Elections Winners" 问题是一个编程挑战，通常出现在算法和数据结构的练习中，特别是在竞赛编程或面试准备中。问题的核心是确定在一次选举中可能获胜的候选人数量。

问题描述

假设有一个选举，其中有多名候选人参选。给你一个数组 votes，其中 votes[i] 表示第 i 个候选人获得的票数。还有一个整数 k，表示尚未计票的选票数量。

你的任务是确定有多少候选人有可能赢得选举。一个候选人如果能在加上尚未计票的 k 票后，票数超过所有其他候选人，那么这个候选人就有可能赢得选举。

输入/输出

• 输入：一个整数数组 votes 和一个整数 k。
• 输出：一个整数，表示有可能赢得选举的候选人数量。

示例

假设 votes = [2, 3, 5, 2]，k = 3。

• 如果所有未计票的票都投给第一个候选人，他们的票数将变为 5，与当前领先者相同，但不足以超过。
• 如果所有未计票的票都投给第二个候选人，他们的票数将变为 6，足以超过所有其他候选人。
• 如果所有未计票的票都投给第三个候选人，他们的票数将变为 8，仍然是领先者。
• 第四个候选人即使获得所有未计票的票，票数也只能达到 5，不足以成为领先者。

因此，有可能赢得选举的候选人数量是 2（第二和第三个候选人）。

解题思路

1. 找出当前票数最多的候选人的票数。
2. 对于每个候选人，计算他们加上 k 票后的票数。
3. 如果这个总票数大于当前票数最多的候选人的票数，或者在 k 为 0 时与最多票数的候选人票数相同但该候选人是唯一的领先者，那么该候选人就有可能赢得选举。
4. 计算满足上述条件的候选人数量。

注意事项

• 如果 k 为 0，那么只有当前票数最多的候选人才有可能赢得选举，除非有多个候选人票数相同且最多，这种情况下这些候选人都有可能赢得选举。
• 问题的解决方案需要考虑到可能的边界情况，比如所有候选人票数相同的情况。

Solution

function solution(votes: number[], k: number): number {
  const max = votes.sort((a, b) => a - b)[votes.length - 1]
  let count = 0

  if (k === 0) {
    const allMax = votes.filter((item) => item === max)

    if (allMax.length === 1) return 1

    return 0
  }

  for (const vote of votes) {
    if (vote + k > max) {
      count++
    }
  }

  return count
}