97 子数组中占绝大多数的元素（1157）

作者: Turbo时间限制: 1S章节: 线段树

晚于: 2020-09-09 12:00:00后提交分数乘系数50%

问题描述 :

实现一个 MajorityChecker 的类，它具有下述两个 API：

1、MajorityChecker(int[] arr) ：用给定的数组 arr 来构造一个 MajorityChecker 的实例。

2、int query(int left, int right, int threshold)

参数为：

0 <= left <= right < arr.length ，其中arr.length表示数组 arr 的长度。

2 * threshold > right - left + 1，也就是说阈值 threshold 始终比子序列长度的一半还要大。

功能：每次查询返回在 arr[left], arr[left+1], ..., arr[right] 中至少出现threshold 次数的元素，如果不存在这样的元素，就返回 -1。

说明：由于threshold 比子序列长度的一半还要大，因此，不可能存在两个元素都出现了threshold 次。

示例：

MajorityChecker majorityChecker = new MajorityChecker([1,1,2,2,1,1]);

majorityChecker.query(0,5,4); // 返回 1

majorityChecker.query(0,3,3); // 返回 -1

majorityChecker.query(2,3,2); // 返回 2

可使用以下main函数：

int main()

{

int n,a,m,left,right, threshold;

vector<int> arr;

cin>>n;

for(int i=0; i<n; i++)

{

cin>>a;

arr.push_back(a);

}

MajorityChecker mc(arr);

cin>>m;

for(int i=0; i<m; i++)

{//在IDE中运行时，输入和输出会交错，这是正常现象

cin>>left;

cin>>right;

cin>>threshold;

int res=mc.query(left, right, threshold) ;

cout<<res<<" ";

}

输入说明 :

首先输入arr数组的长度n，然后输入n个整数，表示arr中的元素

再输入查询的次数m，

然后输入m行，每行是一个查询的参数left, right, threshold，用空格分隔。

提示：

1 <= n <= 20000

1 <= arr[i] <= 20000

对于每次查询，0 <= left <= right < n

对于每次查询，2 * threshold > right - left + 1

m<=10000

输出说明 :

输出m个整数，对应m次查询的结果，每个整数后有一个空格。

输入范例 :

6 1 1 2 2 1 1 3 0 5 4 0 3 3 2 3 2

输出范例 :

1 -1 2

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
class MajorityChecker {
public:
    unordered_map<int, vector<int>> map;
    
    MajorityChecker(vector<int>& arr) {
      for (auto i = 0; i < arr.size(); ++i) map[arr[i]].push_back(i);
    }
    
    int query(int left, int right, int threshold) {
      for (auto &temp : map) {
        if (temp.second.size() < threshold) continue;
        auto m= lower_bound(begin(temp.second), end(temp.second), left);
        auto n = upper_bound(begin(temp.second), end(temp.second), right);
        if (n - m >= threshold) return temp.first;
      }
      return -1;
    }
};
int main()
{
    int n,a,m,left,right, threshold;
    vector<int> arr;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>a;
        arr.push_back(a);
    }
    MajorityChecker mc(arr);
    cin>>m;
    for(int i=0; i<m; i++)
    {//在IDE中运行时，输入和输出会交错，这是正常现象
        cin>>left;
        cin>>right;
        cin>>threshold;
        int res=mc.query(left, right, threshold) ;
        cout<<res<<" ";
    }
}
//lower_bound(起始地址，结束地址，要查找的数值) 返回的是数值 第一个 出现的位置。
//upper_bound(起始地址，结束地址，要查找的数值) 返回的是数值 最后一个 出现的位置。
//binary_search(起始地址，结束地址，要查找的数值) 返回的是是否存在这么一个数，是一个bool值。
/*
int ia[] = {0,1,2,3,4,5,6,7,8,9};
int *beg = begin(ia);
int *last  = end(ia);
上面代码中begin()返回的是数组首元素的指针，
end()返回的是尾元素的下一位置的指针。
这是C++11 为我们提供的两个非常方便的定位数组指针的函数。

*/