数组中有一个数字出现的次数超过了数组长度的一半，找出这个数

看到这个题，我的第一思路是：哈希表记录每个元素出现的次数，还有排序，然后取中间的元素。

看了其他人的博客，发现还有一种巧妙的方法是一遍扫描法。

总结解题思路：

1.哈希。

2.排序。

3.一遍扫描：这个算法的时间复杂度是O(n)，另外用了两个辅助变量。
     k用于临时存储数组中的数据，j用于存储某个数出现的次数。
     开始时k存储数组中的第一个数,j为0，如果数组出现的数于k相等，则j加1，否则就减1，如果j为0，就把当前数组中的数赋给k。

        因为指定的数出现的次数大于数组长度的一半，所有j++与j--相抵消之后，最后j的值是大于等于1的，k中存的那个数就是出现最多的那个数。

代码：

int find1(int a[],int len)//排序后取中间元素  
{  
    sort(a,a+len);  
    return a[len/2];  
}  

int find2(int a[], int len)//哈希map 统计  
{  
    map<int,int> imap;  
    map<int,int>::iterator it ;  
    for(int i=0;i<len;i++)  
    {  
        it = imap.find(a[i]);  
        if(it!=imap.end())  
        {  
            (*it).second++;  
        }else{  
            imap[a[i]] = 1;  
        }  
    }  
  
    it = imap.begin();  
    while(it!=imap.end())  
    {  
        if((*it).second > len/2)  
            return (*it).first;  
        it++;  
    }  
    return -1;  
}  

int find3(int a[] ,int len)//一遍扫描法  
{  
    int tmp = a[0];  
    int count = 1;  
    for(int i=1;i<len;i++)  
    {  
        if(count == 0)  
        {     
            tmp = a[i];  
            count++;  
            continue;  
        }  
        if(a[i] == tmp)  
            count++;  
        else{  
            count--;  
        }  
    }  
    return tmp;  
}  

最后

以上就是自觉咖啡豆为你收集整理的数组中有一个数字出现的次数超过了数组长度的一半，找出这个数的全部内容，希望文章能够帮你解决数组中有一个数字出现的次数超过了数组长度的一半，找出这个数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。