主要元素求法及优化

在一本书中，我看到这样一道题：已知一个数组中有一个元素的出现次数占所有元素个数一半以上，找出这个元素。

我想：真简单！

是的，两个for循环能解决的问题，的确不能说难。

但是，两个for循环的确有些浪费，效率也奇低，有点儿“拿不出手”，所以我开始思索如何简化算法（日常思索）：

突然我心生一计：既然出现的频率这么高，那我对这个数组排完序，出现在中间的数不就是这个主要元素吗？

1. 假设数组为：5 4 3 3 3 2 3 1 3  
2. 排完序后为：1 2 3 3 3 3 3 4 5

这样这个算法的时间复杂度就完全取决于我排序算法的时间复杂度了

真是令人振奋呢：排序有三种不同时间复杂度的：

排序方法	复杂度	推荐程度
冒泡排序	O(N^2)	**
桶排序	O(N)	**
快速排序	O(NlogN)	***
…	…	…

当然这里只推荐快排，因为我们给出的数值范围不确定，这样桶排序极其容易浪费掉大量内存，也是“拿不出手”的。

但是快排的时间复杂度也不能说是很低，能不能更加简化呢？比如说O(N)或者O(logN)？

好吧，我们是理智人，O(logN)就有点逆天，毕竟读入数组就不止这个复杂度了。

所以我们重点讨论O(N)的情形：

消除法：因为占的”份额”实在是多，所以主要元素就是与其他元素一一消除，最终剩下的数也绝对是主元素，所以我们可以考虑用这个方法来“消”出这个主要元素。

这样我们就创造一个计数器k，当遇到相同元素+1，不同减一，很容易知道最终结果必为正数。不过中间过程中会遇到为0的情况，这样我们就初始化k的值，并且把他的指向保存到下一位就行了。

在指完整个数组后，最近保存的指向肯定就是主要元素啦！（想想为什么）

代码附上：

#include <stdio.h>
int main()  
{  
    int n;  
    int a[100] = {0};  
    int book = 1;//提供消除依据  
    int i = 0;  
    int num = 0;//记录当前比较的数  
    scanf("%d",&n);  
    for(i=0; i<n; i++)  
    {  
        scanf("%d",&a[i]);  
    }  
    i = 1;  
    if(1 == n);  
    else  
    {  
        while(i<n)  
        {  
            if(a[i] == a[num])  
            {  
                book++;//相等book+1，数组元素向后寻找  
                i++;  
            }  
            else   
            {  
                book--;//不等-1  
                if(!book)  
                {  
                    i++;//book=0时，标记数也之移动  
                    num = i;  
                }  
                else i++;  
            }  
        }  
    }  
    printf("主元素为：%d\n",a[num]);//主要元素肯定是标记的数，输出就行  
    return 0;  
}