超半的数

题目描述
给你n个数，有一个数的出现次数超过一半，请找出这个数。

输入描述：
输入两行。
第一行包含一个整数n
第二行包含n个整数
1 <= n <= 1000, 1 <= <= 1e9

输出描述：
输出一行，包含一个整数。

解题思路：
思路一：排序，由于 n 个数必有一个数出现次数超过一半，因此将 n 个数排序完后，位于中间的数即为所求结果。排序时间复杂度为： 。
思路二：摩尔投票法，设置一个计数器 count初值为1，选择第一个数作为备选结果放入 res 中。从第二个数开始遍历，若 arr[i] == res，则 count++，否则 count--。当 count == 0 时，将 res 换成当前遍历的数 arr[i]。重复这个过程直至结束。则最终在 res 存的数则为所求结果。时间复杂度为： 。
可以这样想，由于 n 个数中必有一个数 x 的次数超过一半，则将所有的 x 与剩余的数作抵消，则 x 必有剩余，至少剩余1个 x 。因此，即使在遍历过程中遇到，res 中的数为所求结果，但刚好 count == 0，也不用担心，就算 res 发生了变化，到最后 res 中的数也必然是正确结果。

C# 代码：

using System;
class Program{
  static void Main(){
      string input;
      string[] tokens;
      while((input = Console.ReadLine()) != null){
          int n = int.Parse(input);
          input = Console.ReadLine();
          tokens = input.Split();
          int[] arr = new int[n];
          for(int i = 0; i < n; i++) arr[i] = int.Parse(tokens[i]);
          int count = 1;
          int res = arr[0];
          for(int i = 1; i < n; i++){
              if(res == arr[i]) count++;
              else count--;
              if(count == 0){
                  res = arr[i];
                  count = 1;
              }
          }
          Console.WriteLine(res);
      }
  }
}