SOJ 4389: http://acm.scu.edu.cn/soj/problem.action?id=4389
题意非常简单：给定一个数组，找出过半的那个元素。刚开始我考虑从中位数入手，因为中位数一定是所求的答案。所以，利用快排找第(n+1)/2个元素，结果超时了。后来参考了别人的算法，这道题是有O(n)的算法的。核心思想是：两个不相等的数抵消，最后一定可以剩下过半的元素。看了别人的代码，有开数组的，有用队列的，实际上都不必。
代码如下：
#include<iostream> using namespace std; int main() { int T; scanf("%d", &T); int n; int i; int result; int temp; int count; while (T--) { scanf("%d", &n); count = 0; for (i = 0; i < n; i++) { scanf("%d", &temp); if (count == 0) { result = temp; count++; } else { if (temp == result) count++; else count--; } } printf("%d\n", result); } return 0; }
参考以下博文：
https://blog.csdn.net/computer_liuyun/article/details/42062223
https://www.cnblogs.com/87hbteo/p/7146007.html
原文：https://www.cnblogs.com/ClearMoonlight/p/10455817.html
