如何在一堆数中找到那个出现次数超过一半的数字

Posted on   |   In   |  

如何在一堆数中找到那个出现次数超过一半的数字

解体思路:遍历数组，选取当前元素作为要测试的数字，向后遍历，如果相等，则个数加一，否则，减一；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//需要注意的是数组中要求的元素的个数一定要超过一半，否则就不对
#include <cstdio>
int exceed(int arr[], int length)
{
    int copys = 0;
    int num = arr[0];

    for(int i = 0 ; i < length; ++i){
        if (copys == 0)
            num = arr[i];
            
        if (num == arr[i])
            copys++;
        else
            --copys;
    }
    return num;
}


int main()
{
    int a[] = {1,3,4,3,6,8,3,3,3,3,9,6,5,3,3,3,3,3};
    int l = sizeof(a)/sizeof(int);
    
    printf("%d\n", exceed(a, l));
    return 0;
}