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

116 阅读 0 评论 77 点赞

我是靠谱客的博主自觉咖啡豆，这篇文章主要介绍数组中有一个数字出现的次数超过了数组长度的一半，找出这个数，现在分享给大家，希望可以做个参考。

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

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

总结解题思路：

1.哈希。

2.排序。

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

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

代码：

复制代码

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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;  
}

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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;  
}