C++博客
尋找眾數(shù)的算法很多，比如用排序，然后打印出array[n/2]就可以了，但最好的只達(dá)到O(n*logn);但要達(dá)到O(n)的話，就要尋找新的方法，借鑒學(xué)C的時(shí)候，統(tǒng)計(jì)一個(gè)字符串（只含小寫的字母）中每個(gè)字母的個(gè)數(shù)的方法：它是為了減少空間的，采用array[a[i]-'a']++(當(dāng)然需要初始化為0)來做得，所以我們也可以采用同樣的思路來做，但是這個(gè)數(shù)組必須是非負(fù)的，因?yàn)樗鰯?shù)組的下標(biāo)，而且這個(gè)數(shù)組的大小必須是比你要輸入數(shù)組的最大的數(shù)要大，否則就會(huì)越界。

 1/**//*
 2  Name:
 3  Copyright:
 4  Author: LonelyTree
 5  Date: 21-09-08 20:31
 6  Description: 就是對(duì)輸入的正整數(shù)的個(gè)數(shù)進(jìn)行統(tǒng)計(jì)，找出其中超過一半的數(shù)字，時(shí)間復(fù)雜度為O(n).
 7*/
 8
 9#include<stdio.h>
10int main()
11{
12    int array[100000],n;
13    int count,temp,i;
14    scanf("%d",&count);
15    while(count--)
16    {
17        scanf("%d",&n);
18        for(i=0;i<100000;i++)
19        {
20            array[i]=0;
21        }
22        for(i=0;i<n;i++)
23        {
24            scanf("%d",&temp);
25            array[temp]++;
26            /**//*printf("temp=%d\n",temp);
27            printf("array[%d]=%d\n",temp,array[temp]);*/
28        }
29        for(i=0;i<100000;i++)
30        {
31            if(array[i]>n/2)
32            {
33                printf("%d\n",i);
34            }
35        }
36    }
37    system("PAUSE");
38    return 0;
39}
40
41
42
43

這個(gè)跟桶排比較像，貌似可以用基數(shù)排序達(dá)到O(n)，這個(gè)有點(diǎn)不會(huì)寫。其實(shí)還有一個(gè)用快速排序的思路做得……
這個(gè)就是后話了！有興趣的話可以在下面討論討論！