C++程序在已排序的数组中检查多数元素

问题： 编写一个函数来查找给定整数x是否出现在n个整数的已排序数组中超过n/2次。

基本上，我们需要编写一个函数，称为isMajority()，它将一个数组（arr[]），一个数组的大小（n）和要搜索的数字（x）作为参数，并在x出现超过n/2次时返回true。

例子：

输入：arr[] = {1, 2, 3, 3, 3, 3, 10}，x = 3
输出：True（在给定的数组中x出现的次数超过n/2）

输入：arr[] = {1, 1, 2, 4, 4, 4, 6, 6}，x = 4
输出：False（在给定的数组中x没有出现超过n/2次）

输入：arr[] = {1, 1, 1, 2, 2}，x = 1
输出：True（在给定的数组中x出现的次数超过n/2）

METHOD 1 (Using Linear Search)

线性搜索元素的第一次出现，查找到它（假设在索引i），检查在索引i + n/2处的元素。如果在i+n/2处存在元素则返回1，否则返回0。

/* C++程序检查已排序数组中的多数元素 */
#include<bits/stdc++.h>
using namespace std;
 
bool isMajority(int arr[], int n, int x)
{
    int i;
 
    /* 根据n（偶数或奇数）获取最后一个索引 */
    int last_index = n % 2 ? (n / 2 + 1): (n / 2);
 
    /* 在arr[]中搜索x的第一次出现*/
    for (i = 0; i < last_index; i++)
    {
       
        /* 检查是否存在x并且出现次数超过n/2
        次 */
        if (arr[i] == x && arr[i + n / 2] == x)
            return 1;
    }
    return 0;
}
 
/* 驱动程序 */
int main()
{
    int arr[] ={1, 2, 3, 4, 4, 4, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    int x = 4;
    if (isMajority(arr, n, x))
        cout <<    x <<" appears more than "<<
                              n/2 << " times in arr[]"<< endl;
    else
        cout <<x <<" does not appear more than" << n/2 <<"  times in arr[]" << endl;
 
return 0;
}
 
// 此代码由shivanisinghss2110贡献```

输出:

4 appears more than 3 times in arr[]

时间复杂度： O(n)

辅助空间： O(1)

因为使用的是常量额外的空间。

METHOD 2 (Using Binary Search)

使用二进制搜索方法找到给定数字的第一次出现。这里二进制搜索的条件很重要。

// C ++程序检查已排序数组中的多数元素
#include 
using namespace std;

//如果在arr [low…high]中存在x
//则返回x的第一个出现的索引，否则返回-1
int _binarySearch（int arr []，int low，
                 int high，int x）;

//如果x在大小为n的arr []中
//出现次数超过n / 2，则返回true
bool isMajority（int arr []，int n，int x）
{
    //在arr []中找到x的第一个出现的索引
    int i = _binarySearch（arr，0，n-1，x）;

    //如果元素根本不存在，则返回false
    if（i == -1）
        返回false;

    //检查该元素是否存在
    //超过n / 2次
    if（（（i + n / 2）<=（n-1））&&
      arr [i + n / 2] == x）
        返回true;
    其他
        返回false;
}

//如果在arr [low…high]中存在x，则返回x的第一个出现的索引，否则返回-1
int _binarySearch（int arr []，int low，
                 int high，int x）
{
    if（high> = low）
    {
        int mid =（low + high）/ 2; / * low +（high-low）/ 2; * /

        / *如果x是以下内容之一，则检查arr [mid]是否为x的第一个出现。
            arr [mid]是第一次出现，如果x是以下内容之一：
            （i）mid == 0且arr [mid] == x
            （ii）arr [mid-1]  arr [mid-1]）&&
            （arr [mid] == x））
            返回中间;
            
        else if（x> arr [mid]）
            返回_binarySearch（arr，（mid + 1），
                                 high，x）;
        其他
            返回_binarySearch（arr，low，
                                （中-1），x）;
    }
    返回-1;
}

//驱动程序代码
int main（）
{
    int arr [] = {1，2，3，3，3，3，10}；
    int n = sizeof（arr）/ sizeof（arr [0]）;
    int x = 3;

    如果（isMajority（arr，n，x））
        cout << x <<“出现超过”
             << n / 2 <<“次在arr []中”
             << endl;
    其他
        cout << x <<“不出现超过”
             << n / 2 <<“次在arr []中”<< endl;

    回来0;
}

//此代码由shivanisinghss2110提供```

输出：

3出现超过3次在arr []中

时间复杂度： O（对数n）

辅助空间： O（1）

由于使用了常量额外空间。

算法范式： 分治

方法3： 如果已经给出数组已排序且存在多数元素，则检查特定元素是否与检查的中间元素相同。

因为多数元素在数组中出现次数超过n / 2次，所以它将始终是中间元素。我们可以使用这个逻辑检查给定的数字是否是多数元素。

#include 
using namespace std;

bool isMajorityElement(int arr[], int n, int key)
{
    if (arr[n / 2] == key)
        return true;
    else
        return false;
}

int main()
{
    int arr[] = {1, 2, 3, 3, 3, 3, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 3;
    if (isMajorityElement(arr, n, x))
        cout << x << "出现超过"
             << n / 2 << "次在arr []中"
             << endl;
    else
        cout << x << "不出现超过"
             << n / 2 << "次在arr []中" << endl;

    return 0;
}

//此代码由shivanisinghss2110提供```

输出