写一个程序，在长度为N的整数型数组a[ ]中寻找出现至少（N/2+1)次的值，如果存在这样的值，例如，如果a[ ]数组由2，3，2，2，2，3，2，1构成，那么程序应该输出2，因为2出现了5次>N/2次。试着想一个办法，使实现这个功能的计算复杂度为线性（即O（N）），如果你想到一个简单的算法使它能在线性复杂度上实现，在a数组由1，2，3，4，5，。。。。直到N，等元素构成，这样情况下，你的算法要进行多少次比较才能够确定在这个数组中不存在符合条件的值

看多大的数据了

排序可以吗

2N次比较 吧

#include <stdio.h>

void foo( const int a[], size_t n )
{
    int candidate = 0;

    size_t cnt = 0;
    for( size_t i=0; i!=n; ++i )
    {
        if( a[i] == candidate )
            ++cnt;
        else if( cnt < 1 )
            candidate = a[i];
        else
            --cnt;
    }

    cnt = 0;
    for( size_t i=0; i!=n; ++i )
    {
        if( a[i] == candidate )
            ++cnt;
    }

    if( cnt > n/2 )
        printf( "the number is: %d\n", candidate );
    else
        puts( "nobody" );
}

int main( void )
{
    int a[] = { 2, 3, 2, 2, 2, 3, 2, 1 };
    foo( a, sizeof(a)/sizeof(*a) );
}

原理是这样的~不知道这样理解对不对~

数据中如果有N/2个相同的元素则必然是连续出现次数最多的~只要找连续出现次数最多的并判断是否满足条件就可以了~

PS:参考r版代码后又新发现了一点就是满足条件的不仅是连续出现次数最多的而且还是在包括不连续的所有片段中的长度也是最长的~所以数组数据就连续和不连续的两个整体~

[此贴子已经被作者于2017-10-16 17:37编辑过]