本文涉及的基础知识点
线段树 绝对众数
本题其它解法
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 * 104
1 <= arr[i] <= 2 * 104
0 <= left <= right < arr.length
threshold <= right - left + 1
2 * threshold > right - left + 1
调用 query 的次数最多为 104
绝对众数
绝对众数是指在给定的N个数据中，如果出现次数最多的数超过总数的一半，则这个数被称为绝对众数。
线段树
线段树查询
查询[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; };
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
