在O(lg n)的时间复杂度内，在已排序的数组中查找主要元素

Question

在O(lg n)的时间复杂度内，在已排序的数组中查找主要元素

3

我正在解决这个问题，看到一些帖子后，我找到了一个使用摩尔投票算法时间复杂度为O(n)的解决方案。多数元素是指出现次数超过数组大小一半的元素。以下是我的o(lg n)时间复杂度代码，请建议它是否符合o(lg n)。由于我刚开始学习编程，欢迎提出建议。

#include <bits/stdc++.h>
#include <algorithm>
using namespace std ;

int binarySearch(vector <int> a, int l, int h){

        if(l - h < a.size() / 2)
            return -1;

        int mid = (l+h)/2;
        int temporaryLow = mid;
        int temporaryHigh = mid;

        while(temporaryLow > 0 && a[temporaryLow] == a[mid])
            temporaryLow--;

        while(temporaryHigh < a.size() && a[temporaryHigh] == a[mid])
            temporaryHigh++;

        if((temporaryHigh -1) - (temporaryLow+1) +1 >= a.size()/2){
            return a[mid];
        }else{

            return max(binarySearch(a,0,temporaryLow),binarySearch(a,temporaryHigh,h));

        }
    }

 int findMajority(vector <int> numbers){

        return binarySearch(numbers , 0, numbers.size());
    }


    int main()
    {
        int n ;     
        vector <int> a ;
    while ((cin >> n) && n != 9999)
    a.push_back(n);

        int majority = findMajority(a);
        cout << majority ;
    }

- thealchemist

2

如果数组已排序并且具有主要元素，则数组中间的元素必须是主要元素。（在排序数组中，相等的元素是连续的。你可以把超过一半的数组元素放在哪里，避免中心位置？） - rici

这是O(1)。如果您不知道数组是否有多数元素，则必须检查候选多数元素的实例是否足够。该验证将需要O(log N)。 - rici

你好 @rici，能否建议一下我的代码是否具有 O(log N) 的时间复杂度，或者在我们不知道数组是否存在主要元素时提出其他方法。 - thealchemist

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Srikanth Chekuri · Accepted Answer

不，它不是O(log n)。二分查找的思想是每次将搜索空间减半，而你的代码没有做到这一点。

如果数组已排序，则主要值可能是中间值。为了验证这一点，让mid成为中间值。

查找mid的lower_bound和upper_bound，检查差异是否大于数组大小的一半。

代码:

#include <vector>
#include <algorithm>

int majorityElement(const std::vector<int> &array) {
    auto size = array.size();
    if (!size)
        throw std::runtime_error("no majority element");
    auto mid = array[size/2];
    // These run in O(lg N) because array is sorted
    auto low_index = std::lower_bound(array.cbegin(), array.cend(), mid);
    auto upp_index = std::upper_bound(array.cbegin(), array.cend(), mid);
    if ((upp_index - low_index) > size/2) 
        return mid;
    throw std::runtime_error("no majority element");
}