Ignatius and the Princess IV

"OK, you are not too bad, em... But you can never pass the next test." feng5166 says.
"I will tell you an odd number N, and then N integers. There will be a special integer among them, you have to tell me which integer is the special one after I tell you all the integers." feng5166 says.
"But what is the characteristic of the special integer?" Ignatius asks.
"The integer will appear at least (N+1)/2 times. If you can't find the right integer, I will kill the Princess, and you will be my dinner, too. Hahahaha....." feng5166 says.
Can you find the special integer for Ignatius?

Input

The input contains several test cases. Each test case contains two lines. The first line consists of an odd integer N(1<=N<=999999) which indicate the number of the integers feng5166 will tell our hero. The second line contains the N integers. The input is terminated by the end of file.

Output

For each test case, you have to output only one line which contains the special number you have found.

Sample Input

5
1 3 2 3 3
11
1 1 1 1 1 5 5 5 5 5 5
7
1 1 1 1 1 1 1

Sample Output

3
5
1

方法1：
题目里已说明，N为奇数，那么当我们将所有的数放到数组里，再进行排序，第N/2个一定是出现次数最多的数（因为这个数出现次数大于N/2），但是排序的时候注意不能用冒泡，会超时，c++中可以直接调用sort函数，c中调用qsort（或者可以自己写一个快排吧...），但是这里的qsort还需要自己写一个用于比较的函数，再传入函数指针。

#include <stdio.h>
#include <stdlib.h>

int a[1000000];//数较大，不用全局会栈溢出报错

int cmp(const void* a, const void* b) {
    return ( *(int *)a - *(int *)b );
}//用sort时用到的函数，具体参考函数指针的知识

int main(int argc, const char * argv[]) {
    
    int N;
    while ( scanf("%d",&N) != EOF ) {
        int i = 0;
        for ( ; i < N; i++) {
            scanf("%d", &a[i]);
        }
        qsort(a, N, sizeof(int), cmp);
        
        printf("%d\n",a[N/2]);
    }
    return 0;
}

方法2：
创建一个数组并初始化为0，当输入一个数时，以这个数为下标，数组的内容+1，例如输入5次3，那么以3为下标的空间内，存储着的是5，意味着有5次出现，最后找哪个数出现的次数大于N/2，输出即可。
但是要注意的是，如果输入完，再查找一遍就会超时，因为有了两个for循环，我们可以在输入数据的同时去查找，即当要输入3时，看一下空间内的数是否已经等于N/2了，若等于，再输入一次，就会大于了，我们把下标也就是这个数存储起来，最后再输入，可以省去一个for的时间。
这个方法与第一个方法相比，更节省时间，因为省去了排序的时间。

#include <stdio.h>

int main(int argc, const char * argv[]) {
    int N;
    while ( scanf("%d",&N) != EOF ) {
        int a[32768] = {0};
        int i = 0;
        int r = 0;
        for (; i < N; i++) {
            int n;
            scanf("%d", &n);
            if (a[n] >= N/2) {
                r = n;
            }
                a[n]++;
        }
        printf("%d\n", r);
    }
}

方法3：
我们将所有数据分成两组，例如输入：
2 4 1 1 2 2 3 2 2
共9个数据，分成两组为：
2 2 2 2 2
4 1 1 3
当 我们每次去掉两个不同的数，最后剩下的数一定是那个特殊的数，即 2。
因此，我们可以在输入时，判断这个数与上一个数是否相同，若不同，我们将这个数与上一个数相互抵消。
那两个数相同时如何处理？在这组数据里我们可以发现，先出现了两个相同的1，再出现了两个相同的2，不能单独消去，所以必须记录下其出现次数来。在出现两个相同的1时，出现一次就加1，当这时再出现与这个数不同的数，再减1。
讲到这里，可以看出，这与栈的原理十分相似。不理解的可以看下图：


输入最后一个数为2时，会发现所有的数都已经抵消，所以2再入栈后，最后剩下的数为2，输入即可。

简单理解为，当读取一个数，与栈底相同时，这个数继续入栈，与这个数不同时，出栈抵消。
那么会出现两种情况，第1组（特殊的数）会叠加数量，第2组（其余的数）也会叠加数量（但最后会被第1组或第二组其他的数抵消），相互抵消后，最后剩下的必定为特殊的数。

在这里可以虚构一个栈来写代码：

#include <stdio.h>
int main(int argc, const char * argv[]) {
    int N;
    while ( scanf("%d",&N) != EOF ) {
        int spec_n = 0;//记录栈底数
        int appear = 0;//记录栈中数量
        int n;//记录每次手动输入的数
        while (N--) {
            scanf("%d", &n);
            if (appear == 0) {//相当于栈空，直接入栈
                appear = 1;//记录当前栈中有多少个数
                spec_n = n;//记录栈底的数
            }
            else {//此时栈中一定有数
                if (n != spec_n) {
                    appear--;
                }
                else {//此次读到的数与栈底的数相同
                    appear++;
                }
            }
        }
        printf("%d\n", spec_n);//最后在栈底的数
    }
}

这个方法与第二个方法时间效率差不多，但是会略微省空间一些，因为不用开辟一个较大的数组。