1499 - 宇宙总统2

题目描述

在某个星球上，宇宙总统的选举规则是：若有N个候选人，选民将以1~N的顺序编号投票。选民可以投两票，第一票可以投给任意一个人，第二票必须投给另一个人（不能投给第一票那个人）。最后票数最多的人将当选为宇宙总统。 如果两个人的票数一样多，那么编号小的人当选。 现在给出N个候选人的编号，请你计算最终当选的宇宙总统的编号。

输入格式

输入文件共一行，包含一个整数N。

输出格式

输出文件共一行，包含一个整数，表示最终当选的宇宙总统的编号。

数据范围

1≤N≤10000

样例

输入样例：
5
输出样例：
2

算法1

(暴力枚举) $O(n^2)$

题目中N的范围最大是1e4，暴力枚举的时间复杂度为O(n^2)，因此可以使用暴力枚举的方式求解。

对于每个人都枚举一遍，对于每个人，再枚举一遍其他人，计算出这两个人的总得票数，如果总得票数大于当前最大得票数，则更新最大得票数和最大得票人的编号。

时间复杂度

暴力枚举的时间复杂度为O(n^2)，可以通过本题。

C++ 代码

算法2

(计数排序) $O(n)$

对于每个候选人的得票数，我们可以开一个桶进行计数，最后再遍历一遍桶，找到得票数最多的人。

时间复杂度

计数排序的时间复杂度为O(n)，可以通过本题。

C++ 代码

算法3

(排序) $O(nlogn)$

对于每个候选人，可以开一个结构体记录编号和得票数，然后将结构体数组按得票数从大到小排序，如果得票数相等，则按照编号从小到大进行排序，排序后第一个结构体的编号即为当选的宇宙总统的编号。

时间复杂度

排序的时间复杂度为O(nlogn)，可以通过本题。

C++ 代码