【线段树】【众数】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个数据中，如果出现次数最多的数超过总数的一半，则这个数被称为绝对众数。

线段树

线段树查询

查询[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++**实现。

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