Design a data structure that efficiently finds the majority element of a given subarray.
The majority element of a subarray is an element that occurs threshold times or more in the subarray.
Implementing the MajorityChecker class:
MajorityChecker(int[] arr) Initializes the instance of the class with the given array arr.
int query(int left, int right, int threshold) returns the element in the subarray arr[left...right] that occurs at least threshold times, or -1 if no such element exists.
We notice that the problem requires us to find the possible majority element in a specific interval, so we consider using a segment tree to maintain the candidate majority element and its occurrence in each interval.
We define each node of the segment tree as Node, each node contains the following attributes:
l: The left endpoint of the node, the index starts from $1$.
r: The right endpoint of the node, the index starts from $1$.
x: The candidate majority element of the node.
cnt: The occurrence of the candidate majority element of the node.
The segment tree mainly has the following operations:
build(u, l, r): Build the segment tree.
pushup(u): Use the information of the child nodes to update the information of the parent node.
query(u, l, r): Query the interval sum.
In the initialization method of the main function, we first create a segment tree, and use a hash table $d$ to record all indexes of each element in the array.
In the query(left, right, threshold) method, we directly call the query method of the segment tree to get the candidate majority element $x$. Then use binary search to find the first index $l$ in the array that is greater than or equal to $left$, and the first index $r$ that is greater than $right$. If $r - l \ge threshold$, return $x$, otherwise return $-1$.
In terms of time complexity, the time complexity of the initialization method is $O(n)$, and the time complexity of the query method is $O(\log n)$. The space complexity is $O(n)$. Here, $n$ is the length of the array.
classNode:__slots__=("l","r","x","cnt")def__init__(self):self.l=self.r=0self.x=self.cnt=0classSegmentTree:def__init__(self,nums):self.nums=numsn=len(nums)self.tr=[Node()for_inrange(n<<2)]self.build(1,1,n)defbuild(self,u,l,r):self.tr[u].l,self.tr[u].r=l,rifl==r:self.tr[u].x=self.nums[l-1]self.tr[u].cnt=1returnmid=(l+r)>>1self.build(u<<1,l,mid)self.build(u<<1|1,mid+1,r)self.pushup(u)defquery(self,u,l,r):ifself.tr[u].l>=landself.tr[u].r<=r:returnself.tr[u].x,self.tr[u].cntmid=(self.tr[u].l+self.tr[u].r)>>1ifr<=mid:returnself.query(u<<1,l,r)ifl>mid:returnself.query(u<<1|1,l,r)x1,cnt1=self.query(u<<1,l,r)x2,cnt2=self.query(u<<1|1,l,r)ifx1==x2:returnx1,cnt1+cnt2ifcnt1>=cnt2:returnx1,cnt1-cnt2else:returnx2,cnt2-cnt1defpushup(self,u):ifself.tr[u<<1].x==self.tr[u<<1|1].x:self.tr[u].x=self.tr[u<<1].xself.tr[u].cnt=self.tr[u<<1].cnt+self.tr[u<<1|1].cntelifself.tr[u<<1].cnt>=self.tr[u<<1|1].cnt:self.tr[u].x=self.tr[u<<1].xself.tr[u].cnt=self.tr[u<<1].cnt-self.tr[u<<1|1].cntelse:self.tr[u].x=self.tr[u<<1|1].xself.tr[u].cnt=self.tr[u<<1|1].cnt-self.tr[u<<1].cntclassMajorityChecker:def__init__(self,arr:List[int]):self.tree=SegmentTree(arr)self.d=defaultdict(list)fori,xinenumerate(arr):self.d[x].append(i)defquery(self,left:int,right:int,threshold:int)->int:x,_=self.tree.query(1,left+1,right+1)l=bisect_left(self.d[x],left)r=bisect_left(self.d[x],right+1)returnxifr-l>=thresholdelse-1# Your MajorityChecker object will be instantiated and called as such:# obj = MajorityChecker(arr)# param_1 = obj.query(left,right,threshold)
classNode{intl,r;intx,cnt;}classSegmentTree{privateNode[]tr;privateint[]nums;publicSegmentTree(int[]nums){intn=nums.length;this.nums=nums;tr=newNode[n<<2];for(inti=0;i<tr.length;++i){tr[i]=newNode();}build(1,1,n);}privatevoidbuild(intu,intl,intr){tr[u].l=l;tr[u].r=r;if(l==r){tr[u].x=nums[l-1];tr[u].cnt=1;return;}intmid=(l+r)>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u);}publicint[]query(intu,intl,intr){if(tr[u].l>=l&&tr[u].r<=r){returnnewint[]{tr[u].x,tr[u].cnt};}intmid=(tr[u].l+tr[u].r)>>1;if(r<=mid){returnquery(u<<1,l,r);}if(l>mid){returnquery(u<<1|1,l,r);}varleft=query(u<<1,l,r);varright=query(u<<1|1,l,r);if(left[0]==right[0]){left[1]+=right[1];}elseif(left[1]>=right[1]){left[1]-=right[1];}else{right[1]-=left[1];left=right;}returnleft;}privatevoidpushup(intu){if(tr[u<<1].x==tr[u<<1|1].x){tr[u].x=tr[u<<1].x;tr[u].cnt=tr[u<<1].cnt+tr[u<<1|1].cnt;}elseif(tr[u<<1].cnt>=tr[u<<1|1].cnt){tr[u].x=tr[u<<1].x;tr[u].cnt=tr[u<<1].cnt-tr[u<<1|1].cnt;}else{tr[u].x=tr[u<<1|1].x;tr[u].cnt=tr[u<<1|1].cnt-tr[u<<1].cnt;}}}classMajorityChecker{privateSegmentTreetree;privateMap<Integer,List<Integer>>d=newHashMap<>();publicMajorityChecker(int[]arr){tree=newSegmentTree(arr);for(inti=0;i<arr.length;++i){d.computeIfAbsent(arr[i],k->newArrayList<>()).add(i);}}publicintquery(intleft,intright,intthreshold){intx=tree.query(1,left+1,right+1)[0];intl=search(d.get(x),left);intr=search(d.get(x),right+1);returnr-l>=threshold?x:-1;}privateintsearch(List<Integer>arr,intx){intleft=0,right=arr.size();while(left<right){intmid=(left+right)>>1;if(arr.get(mid)>=x){right=mid;}else{left=mid+1;}}returnleft;}}/** * Your MajorityChecker object will be instantiated and called as such: * MajorityChecker obj = new MajorityChecker(arr); * int param_1 = obj.query(left,right,threshold); */
classNode{public:intl=0,r=0;intx=0,cnt=0;};usingpii=pair<int,int>;classSegmentTree{public:SegmentTree(vector<int>&nums){this->nums=nums;intn=nums.size();tr.resize(n<<2);for(inti=0;i<tr.size();++i){tr[i]=newNode();}build(1,1,n);}piiquery(intu,intl,intr){if(tr[u]->l>=l&&tr[u]->r<=r){return{tr[u]->x,tr[u]->cnt};}intmid=(tr[u]->l+tr[u]->r)>>1;if(r<=mid){returnquery(u<<1,l,r);}if(l>mid){returnquery(u<<1|1,l,r);}autoleft=query(u<<1,l,r);autoright=query(u<<1|1,l,r);if(left.first==right.first){left.second+=right.second;}elseif(left.second>=right.second){left.second-=right.second;}else{right.second-=left.second;left=right;}returnleft;}private:vector<Node*>tr;vector<int>nums;voidbuild(intu,intl,intr){tr[u]->l=l;tr[u]->r=r;if(l==r){tr[u]->x=nums[l-1];tr[u]->cnt=1;return;}intmid=(l+r)>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u);}voidpushup(intu){if(tr[u<<1]->x==tr[u<<1|1]->x){tr[u]->x=tr[u<<1]->x;tr[u]->cnt=tr[u<<1]->cnt+tr[u<<1|1]->cnt;}elseif(tr[u<<1]->cnt>=tr[u<<1|1]->cnt){tr[u]->x=tr[u<<1]->x;tr[u]->cnt=tr[u<<1]->cnt-tr[u<<1|1]->cnt;}else{tr[u]->x=tr[u<<1|1]->x;tr[u]->cnt=tr[u<<1|1]->cnt-tr[u<<1]->cnt;}}};classMajorityChecker{public:MajorityChecker(vector<int>&arr){tree=newSegmentTree(arr);for(inti=0;i<arr.size();++i){d[arr[i]].push_back(i);}}intquery(intleft,intright,intthreshold){intx=tree->query(1,left+1,right+1).first;autol=lower_bound(d[x].begin(),d[x].end(),left);autor=lower_bound(d[x].begin(),d[x].end(),right+1);returnr-l>=threshold?x:-1;}private:unordered_map<int,vector<int>>d;SegmentTree*tree;};/** * Your MajorityChecker object will be instantiated and called as such: * MajorityChecker* obj = new MajorityChecker(arr); * int param_1 = obj->query(left,right,threshold); */
typenodestruct{l,r,x,cntint}typesegmentTreestruct{nums[]inttr[]*node}typepairstruct{x,cntint}funcnewSegmentTree(nums[]int)*segmentTree{n:=len(nums)tr:=make([]*node,n<<2)fori:=rangetr{tr[i]=&node{}}t:=&segmentTree{nums,tr}t.build(1,1,n)returnt}func(t*segmentTree)build(u,l,rint){t.tr[u].l,t.tr[u].r=l,rifl==r{t.tr[u].x=t.nums[l-1]t.tr[u].cnt=1return}mid:=(l+r)>>1t.build(u<<1,l,mid)t.build(u<<1|1,mid+1,r)t.pushup(u)}func(t*segmentTree)query(u,l,rint)pair{ift.tr[u].l>=l&&t.tr[u].r<=r{returnpair{t.tr[u].x,t.tr[u].cnt}}mid:=(t.tr[u].l+t.tr[u].r)>>1ifr<=mid{returnt.query(u<<1,l,r)}ifl>mid{returnt.query(u<<1|1,l,r)}left,right:=t.query(u<<1,l,r),t.query(u<<1|1,l,r)ifleft.x==right.x{left.cnt+=right.cnt}elseifleft.cnt>=right.cnt{left.cnt-=right.cnt}else{right.cnt-=left.cntleft=right}returnleft}func(t*segmentTree)pushup(uint){ift.tr[u<<1].x==t.tr[u<<1|1].x{t.tr[u].x=t.tr[u<<1].xt.tr[u].cnt=t.tr[u<<1].cnt+t.tr[u<<1|1].cnt}elseift.tr[u<<1].cnt>=t.tr[u<<1|1].cnt{t.tr[u].x=t.tr[u<<1].xt.tr[u].cnt=t.tr[u<<1].cnt-t.tr[u<<1|1].cnt}else{t.tr[u].x=t.tr[u<<1|1].xt.tr[u].cnt=t.tr[u<<1|1].cnt-t.tr[u<<1].cnt}}typeMajorityCheckerstruct{tree*segmentTreedmap[int][]int}funcConstructor(arr[]int)MajorityChecker{tree:=newSegmentTree(arr)d:=map[int][]int{}fori,x:=rangearr{d[x]=append(d[x],i)}returnMajorityChecker{tree,d}}func(this*MajorityChecker)Query(leftint,rightint,thresholdint)int{x:=this.tree.query(1,left+1,right+1).xl:=sort.SearchInts(this.d[x],left)r:=sort.SearchInts(this.d[x],right+1)ifr-l>=threshold{returnx}return-1}/** * Your MajorityChecker object will be instantiated and called as such: * obj := Constructor(arr); * param_1 := obj.Query(left,right,threshold); */