检查排好序的数组中是否有元素的个数超过数组数目的一半

问题：设计一个函数，检查升序数组中是存在其出现次数超过数组长度一半的元素。

 

分析：以数组{0,1,1,1,3}为例，元素1的出现次数为3，数组的长度为5，则此函数返回true。对于数组{0,1,1,1,3, 5}，数组的长度为6，所以此情况下，函数返回false。

 

最直观的解法是从头开始遍历数组，统计出现重复出现的元素个数，若其统计结果大于n/2，则返回true。此方法在最坏情况下算法复杂度为n。

 

通过观察数组可以看到，若有元素重复出现的次数大于n/2，则此元素必定出现在n/2处。因此算法可以改进为从n/2处开始向前和先后搜索。经此改进后的时间复杂度为n/2。

 

改进后的算法仍不理想，还有待提高的空间。由于是在有序数组中查找，因此可以使用二分搜索来查找第一次中间值出现的位置index，然后检查a[index + n/2]是否等于a[n/2]，若等于则返回true。此算法的时间复杂度为log(n/2)。

 

算法实现如下：

bool IsGreaterThanHalfInArray(int array[], int n)
{
    if (array == NULL || n <1)
        return false;

    if (n == 1)
        return true;

    // 取中间数
    int m;
    if (n & 0x1 == 1)
        m = n >> 1;
    else
        m = (n >> 1) - 1;
       
    int mid = array[m];
    int index = BinarySearch::SearchFirst(array, (n >> 1) + 1, mid);

    if (array[(n >> 1) +  index] == mid)
        return true;
    else
        return false;
}

 

文件:	algorithm.zip
大小:	16KB
下载:	下载