【线段树】【众数】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 * 104
1 <= arr[i] <= 2 * 104
0 <= left <= right < arr.length
threshold <= right - left + 1
2 * threshold > right - left + 1
调用 query 的次数最多为 104

绝对众数

绝对众数是指在给定的N个数据中，如果出现次数最多的数超过总数的一半，则这个数被称为绝对众数。
性质一：假定n个数有绝对众数z，则将n个数任意分成m组，则z至少是一组的绝对众数。
令这个m组的数量分别为n1,n2, ⋯ \cdots ⋯ nm，则 ∑ x : 1 m \sum_{x:1}^m ∑x:1m​nx == n 。
令z在这些组出现的次数分别为z1,z2, ⋯ 4 z m 。假定 z 不是这 m 组的绝对众数，则 \cdots4 zm。 假定z不是这m组的绝对众数，则 ⋯4zm。假定z不是这m组的绝对众数，则{\forall} x x x\in$[1,m] 2*nx <= nx。
故 2 × ∑ x : 1 m z x 2 \times \sum_{x:1}^mzx 2×∑x:1m​zx <= ∑ x : 1 m n x \sum_{x:1}^mnx ∑x:1m​nx → \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;
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80

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

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;
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141

扩展阅读

视频课程

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

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

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

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

测试环境

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

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览60345 人正在系统学习中
群中有博文配套源码
QQ群名片
注：本文转载自blog.csdn.net的闻缺陷则喜何志丹的文章"https://blog.csdn.net/he_zhidan/article/details/137073469"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！