【线段树】【众数】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

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

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

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

本文涉及的基础知识点

本题其它解法

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

绝对众数

线段树

线段树查询

线段树建树

代码

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

扩展阅读

视频课程

相关下载

测试环境

网站公告

今日签到

热门文章

最新发布