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

题目

设计一个数据结构，有效地找到给定子数组的多数元素。
子数组的多数元素是在子数组中出现 threshold 次数或次数以上的元素。
实现 MajorityChecker 类:
MajorityChecker(int[] arr) 会用给定的数组 arr 对 MajorityChecker 初始化。
int query(int left, int right, int threshold) 返回子数组中的元素 arr[left…right] 至少出现 threshold 次数，如果不存在这样的元素则返回 -1。
示例 1：
输入:
[“MajorityChecker”, “query”, “query”, “query”]
[[[1, 1, 2, 2, 1, 1]], [0, 5, 4], [0, 3, 3], [2, 3, 2]]
输出：
[null, 1, -1, 2]
解释：
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
参数范围：
1 <= arr.length <= 2 * 104
1 <= arr[i] <= 2 * 104
0 <= left <= right < arr.length
threshold <= right - left + 1
2 * threshold > right - left + 1
调用 query 的次数最多为 104

分析

时间复杂度

O(nsqrt(n)log(sqrt(n))

分两种情况分别讨论。

threshold <= 100

说明 right - left + 1 < 200。直接遍历arr[left,right]，统计众数。

threshold > 100

出现次数超过100的数，不会超过200个。记录这些数的索引。然后二分查找[0,right+1)的数量和[0,left)的数量，两者相减就是nums[left,right]中此数的数量。

变量解释


len	sqrt(数组长度)代替100
m_vMoreValues	记录出现次数超过len的数
m_vValueIndexs	记录各数的索引，比如：m_vValueIndexs[3]记录所有3的索引。

可以用摩尔投票

稍稍降低空间复杂度

代码

核心代码

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);

//CConsole::Out(res);

}

2023年3月旧代码

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,直接遍历
};

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

洒家想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
墨家名称的来源：有所得以墨记之。
如果程序是一条龙，那算法就是他的是睛