【线段树】【众数】1157数组中占绝大多数的元素

本文主要是介绍【线段树】【众数】1157数组中占绝大多数的元素，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本文涉及的基础知识点

线段树绝对众数

本题其它解法

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

LeetCode1157数组中占绝大多数的元素

设计一个数据结构，有效地找到给定子数组的多数元素。
子数组的多数元素是在子数组中出现 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 * 10⁴
1 <= arr[i] <= 2 * 10⁴
0 <= left <= right < arr.length
threshold <= right - left + 1
2 * threshold > right - left + 1
调用 query 的次数最多为 10⁴

绝对众数

绝对众数是指在给定的N个数据中，如果出现次数最多的数超过总数的一半，则这个数被称为绝对众数。
性质一：假定n个数有绝对众数z，则将n个数任意分成m组，则z至少是一组的绝对众数。
令这个m组的数量分别为n1,n2, $\cdots$ nm，则 $\sum_{x:1}^m$ nx == n 。
令z在这些组出现的次数分别为z1,z2, $\cdots4 zm。假定z不是这m组的绝对众数，则$ {\forall} $x$ \in$[1,m] 2*nx <= nx。
故 $\times \sum_{x:1}^mzx$ <= $\sum_{x:1}^mnx$ $\rightarrow$ z不是绝对众数 $\rightarrow$ 和假设矛盾

线段树

线段树查询

查询[left,r]时，最多查询4种类型的节点，每种节点都不超过logn。
一，l及其祖先。
二，r及其祖先。
三,类型一的兄弟节点。
四，类型二的兄弟节点。
根据性质一，查询这四类节点的众数是否是[l,r]的众数。[l,r]必须有众数，且众数出现的次数>= threshold。m_vIndexs 按升序记录各数值出现的次数。利用二分查找看[l,r]中x出现的次数。

线段树建树

长度为1的节点是{nums[iSaveLeft-1],1}
长度不为1的节点看子节点的众数是否是本节点的众数。

代码

class CMyLineTree
{
public:CMyLineTree(vector<int>& arr):m_vNode(arr.size()*4), m_iSize(arr.size()){const int iMax = *std::max_element(arr.begin(), arr.end());m_vIndexs.resize(iMax + 1);for (int i = 0; i < arr.size(); i++){m_vIndexs[arr[i]].emplace_back(i);}Init(1,1, arr.size(), arr);}int Query( int left, int r, int threshold){vector<int> vCan;Query(vCan, 1, 1, m_iSize, left+1, r+1);auto [i1, i2] = Query(left, r, vCan);return (i2 >= threshold) ? i1 : -1;}
protected:std::pair<int, int> Query(int left, int r, vector<int> vCan){for (const auto& n : vCan){if (-1 == n) {continue;}auto it1 = std::lower_bound(m_vIndexs[n].begin(), m_vIndexs[n].end(), left);auto it2 = std::upper_bound(m_vIndexs[n].begin(), m_vIndexs[n].end(), r);const int iCnt = it2 - it1;if (2 * iCnt > (r - left + 1)){return { n,iCnt };}}return { -1,0 };}void Query(vector<int>& vCan,int iNode,int iSaveLeft,int iSaveRight, int left, int r){if ((left <= iSaveLeft) && (iSaveRight <= r)){vCan.push_back(m_vNode[iNode].first);return;}const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;if (mid >= left){Query(vCan, iNode * 2, iSaveLeft, mid, left, r);}if (mid + 1 <= r) {Query(vCan, iNode * 2+1, mid+1, iSaveRight, left, r);}}void Init(int iNode, const int iSaveLeft, const int iSaveRight,const vector<int>& arr){if (iSaveLeft == iSaveRight){m_vNode[iNode] = { arr[iSaveLeft - 1],1 };return;}const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;Init(iNode * 2, iSaveLeft, mid,arr);Init(iNode * 2 + 1, mid+1, iSaveRight,arr);m_vNode[iNode] = Query(iSaveLeft-1, iSaveRight-1, { m_vNode[2*iNode].first,m_vNode[2 * iNode+1].first });}	vector<pair<int,int>> m_vNode;vector<vector<int>> m_vIndexs;const int m_iSize;
};class MajorityChecker {
public:MajorityChecker(vector<int>& arr):m_lineTree(arr){}int query(int left, int right, int threshold) {return m_lineTree.Query(left, right, threshold);}CMyLineTree m_lineTree;
};

再次封装：拆分新类求众数

template<class TSave,class TRecord>
class CSingUpdateLineTree
{
public:CSingUpdateLineTree(int iEleSize):m_iEleSize(iEleSize), m_vSave(iEleSize*4){}void Update(int index, TRecord update) {Update(1, 1, m_iEleSize, index + 1, update);}void Query(int leftIndex, int leftRight) {Query(1, 1, m_iEleSize, leftIndex + 1, leftRight + 1);}void Init() {Init(1, 1, m_iEleSize);}const int m_iEleSize;
protected:void Init(int iNodeNO, int iSaveLeft, int iSaveRight){if (iSaveLeft == iSaveRight) {OnInit(m_vSave[iNodeNO], iSaveLeft);return;}const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;Init(iNodeNO * 2, iSaveLeft, mid);Init(iNodeNO * 2+1, mid+1, iSaveRight);OnUpdateParent(m_vSave[iNodeNO], m_vSave[iNodeNO * 2], m_vSave[iNodeNO * 2 + 1], iSaveLeft, iSaveRight);}void Query(int iNodeNO, int iSaveLeft, int iSaveRight, int iQueryLeft,int iQueryRight) {if (( iSaveLeft >= iQueryLeft) && (iSaveRight <= iQueryRight )) {OnQuery(m_vSave[iNodeNO]);return;}if (iSaveLeft == iSaveRight) {//没有子节点return;}const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;if (mid >= iQueryLeft) {Query(iNodeNO * 2, iSaveLeft, mid, iQueryLeft, iQueryRight);}if( mid+1 <= iQueryRight ){Query(iNodeNO * 2+1, mid+1, iSaveRight, iQueryLeft, iQueryRight);}}void Update(int iNodeNO,int iSaveLeft,int iSaveRight,int iUpdateNO, TRecord update) {if (iSaveLeft == iSaveRight){OnUpdate(m_vSave[iNodeNO], update);return;}const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;if (iUpdateNO <= mid) {Update(iNodeNO * 2, iSaveLeft, mid, iUpdateNO, update);}else {Update(iNodeNO * 2+1, mid+1, iSaveRight, iUpdateNO, update);}OnUpdateParent(m_vSave[iNodeNO], m_vSave[iNodeNO * 2], m_vSave[iNodeNO * 2+1],iSaveLeft,iSaveRight);}virtual void OnInit(TSave& save,int iSave)=0;virtual void OnQuery(TSave& save) = 0;virtual void OnUpdate(TSave& save, const TRecord& update) = 0;virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r,int iSaveLeft,int iSaveRight) = 0;vector<TSave> m_vSave;
};class CMoreNum
{
public:CMoreNum(const vector<int>& arr) {const int iMax = *std::max_element(arr.begin(), arr.end());m_vIndexs.resize(iMax + 1);for (int i = 0; i < arr.size(); i++){m_vIndexs[arr[i]].emplace_back(i);}}std::pair<int, int> Query(int left, int r, vector<int> vCan){for (const auto& n : vCan){if (-1 == n) {continue;}auto it1 = std::lower_bound(m_vIndexs[n].begin(), m_vIndexs[n].end(), left);auto it2 = std::upper_bound(m_vIndexs[n].begin(), m_vIndexs[n].end(), r);const int iCnt = it2 - it1;if (2 * iCnt > (r - left + 1)){return { n,iCnt };}}return { -1,0 };}vector<vector<int>> m_vIndexs;
};template<class TSave = std::pair<int,int>, class TRecord = int >
class CMyLineTree : public CSingUpdateLineTree<TSave, TRecord>
{
public:CMyLineTree(const vector<int>& arr):m_moreNum(arr),CSingUpdateLineTree<TSave,TRecord>(arr.size()){m_arr = arr;		CSingUpdateLineTree<TSave, TRecord>::Init();}int Query(int left, int r, int threshold){m_vCan.clear();CSingUpdateLineTree<TSave, TRecord>::Query(left,r);auto [i1, i2] = m_moreNum.Query(left, r, m_vCan);return (i2 >= threshold) ? i1 : -1;}
protected:vector<int> m_vCan;virtual void OnQuery(TSave& save) override	{m_vCan.emplace_back(save.first);}virtual void OnUpdate(TSave& save, const TRecord& update) override{};virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) override	{vector<int> vCan = { left.first,r.first };par = m_moreNum.Query(iSaveLeft - 1, iSaveRight - 1, vCan);}	vector<int> m_arr;CMoreNum m_moreNum;virtual void OnInit(TSave& save, int iSave) override	{save = { m_arr[iSave - 1],1 };}
};class MajorityChecker {
public:MajorityChecker(vector<int>& arr) :m_lineTree(arr) {}int query(int left, int right, int threshold) {return m_lineTree.Query(left, right, threshold);}CMyLineTree<> m_lineTree;
};

扩展阅读

视频课程

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

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

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛