C++二分查找算法：数组中占绝大多数的元素

class MajorityChecker {
public:
MajorityChecker(vector& arr) {
m_arr = arr;
m_c = arr.size();
m_len = sqrt(m_c);
const int iMax = *std::max_element(arr.begin(),arr.end());
m_vValueIndexs.resize(iMax+1);
for (int i = 0 ; i < m_c ;i++)
{
const auto& n = arr[i];
m_vValueIndexs[n].emplace_back(i);
}
for (int i = 0; i <= iMax; i++)
{
if (m_vValueIndexs[i].size() >= m_len)
{
m_vMoreValues.emplace_back(i);
}
}
}
int query(int left, int right, int threshold) {
if (threshold >= m_len)
{
for (const auto n : m_vMoreValues)
{
//[0,left)的数量
auto it1 = std::lower_bound(m_vValueIndexs[n].begin(), m_vValueIndexs[n].end(), left);
//[0,right+1)的数量
auto it2 = std::lower_bound(m_vValueIndexs[n].begin(), m_vValueIndexs[n].end(), right+1);
if (it2 - it1 >= threshold)
{
return n;
}
}
return -1;
}
std::unordered_map<int, int> mValueNum;
for (int i = left; i <= right; i++)
{
mValueNum[m_arr[i]]++;
}
for (const auto it : mValueNum)
{
if (it.second >= threshold)
{
return it.first;
}
}
return -1;
}
vector m_arr;
vector<vector> m_vValueIndexs;
vector m_vMoreValues;
int m_c;
int m_len;
};

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}
int main()
{
vector nums = { 1, 1, 2, 2, 1, 1 };
MajorityChecker majorityChecker(nums);
int res = majorityChecker.query(0, 5, 4); // 返回 1
assert(1 , res);
majorityChecker.query(0, 3, 3); // 返回 -1
assert(-1, res);
majorityChecker.query(2, 3, 2); // 返回 2
assert(2, res);

class MajorityChecker {
public:
MajorityChecker(vector& arr) :m_iNumRange(sqrt(arr.size()) * 2), m_c(arr.size()), m_arr(arr)
{
Init(arr);
}
void Init(const vector& arr)
{
std::unordered_map<int, int> mValueNums;
for (const auto& a : arr)
{
mValueNums[a]++;
}
for (const auto& it : mValueNums)
{
if (it.second <= m_iNumRange)
{
continue;
}
m_vValues.emplace_back(it.first);
m_vValueIndexs.emplace_back();
m_vValueIndexs.back().emplace_back(0);
for (int i = 0; i < m_c; i++)
{
int iSame = arr[i] == it.first;
m_vValueIndexs.back().emplace_back(iSame + m_vValueIndexs.back().back());
}
}
}
int query(int left, int right, int threshold) {
const int len = right - left + 1;
//直接读取缓存
if (threshold > m_iNumRange)
{
for (int i = 0; i < m_vValueIndexs.size(); i++)
{
const int iNum = m_vValueIndexs[i][right + 1] - m_vValueIndexs[i][left];
if (iNum >= threshold)
{
return m_vValues[i];
}
}
return -1;
}
//暴力遍历
int iValue = -1, iNum = 0;
for (int i = left; i <= right; i++)
{
if (m_arr[i] == iValue)
{
iNum++;
}
else
{
if (0 == iNum)
{
iValue = m_arr[i];
iNum = 1;
}
else
{
iNum–;
}
}
}
iNum = 0;
for (int i = left; i <= right; i++)
{
if (m_arr[i] == iValue)
{
iNum++;
}
}
return (iNum >= threshold) ? iValue : -1;
}
//缓存各数值的前缀和
std::vector m_vValues;//m_vValues[i]对应 m_vValueIndexs[i]的值
vector<vector> m_vValueIndexs;
vector m_arr;
const int m_c;
const int m_iNumRange = 1;//众数的数量小于等于m_iNumRange,直接遍历
};