Best (fastest) way to find the number most commonly entered in C?

Question

Well, I think the name basically explains my doubts. I will have the numbers n , these n numbers go from 1 to x , where x is not more than 10 ⁵ . What is fast (less time to start it) to find out which number has been added more times? This , knowing that the number that appears most often, appears more than half the time .

What I have tried so far:

//for (1<=x<=10⁵)
int v[100000+1];

//multiple instances , ends when n = 0
while (scanf("%d", &n)&&n>0) {
    zerofill(v);
    for (i=0; i<n; i++) {
        scanf("%d", &x);
        v[x]++;
        if (v[x]>n/2)
            i=n;
    }
    printf("%d\n", x);
}

Zero filling the array of positions x and increasing the position vector [x] and at the same time checking that the vector [x] is greater than n / 2, it is not fast enough.

, .

: .

Answer 1

O(n), , , . , , n x, , ..

, "", , , , , , , , n x.

, x , .

, ( , ), ( ):

• initialize count = 0
• if count is 0, champion = element count = 1
• else if element != champion count
• else increment count

champion , .

, ,

for (int i=0,n=size; i<n; i++) {
    if (++count[x[i]] > half) return x[i];
}

.

, , , , , , - (100000 - ).

Answer 2

, , , , , n/2