[英雄星球六月集训LeetCode解题日报] 第15日 树状数组
日报
- 第一题不会用树状数组，写个线段树吧。
- 第二题有点像逆序对。
题目
一、 1157. 子数组中占绝大多数的元素
1. 题目描述
设计一个数据结构，有效地找到给定子数组的 多数元素 。
子数组的 多数元素 是在子数组中出现 threshold 次数或次数以上的元素。
实现 MajorityChecker 类:
- MajorityChecker(int[] arr) 会用给定的数组 arr 对 MajorityChecker 初始化。
- int query(int left, int right, int threshold) 返回子数组中的元素 arr[left…right] 至少出现 threshold 次数，如果不存在这样的元素则返回 -1。
2. 思路分析
通过英文，我们发现这像是主元素问题。
-
那么它询问时，threshold参数一定超过这个询问区间的一半。
-
我们用线段树维护每个区间从出现最多的两个元素，以及他们出现的次数。
- 显然，第i个叶子节点的值是Counter({num[i-1]:1})，(i从1计数)
- 左右孩子pushup时，把两边的Counter合并，然后取剩下的最多两个元素。
- 最后查询出来后，判断最多的那个元素是否符合题意即可，不符合就返回-1。
-
为什么要维护两个元素呢，因为如果子区间存在a,b出现次数相同，都是这个区间长度的一半，那么这两个数都可能对父区间造成贡献。
3. 代码实现
class IntervalTree:
def __init__(self, size,nums=None):
self.size = size
self.nums = nums
self.interval_tree = [None for _ in range(size*4)]
# self.cnt = [Counter() for _ in range(size*4)]
if nums:
self.build_tree(1,1,size)
def build_tree(self,p,l,r):
interval_tree = self.interval_tree
nums = self.nums
if l == r:
interval_tree[p] = Counter([nums[l-1]])
return
mid = (l+r)//2
self.build_tree(p*2,l,mid)
self.build_tree(p*2+1,mid+1,r)
interval_tree[p] = Counter(dict((interval_tree[p*2]+interval_tree[p*2+1]).most_common(2)))
def query(self,p,l,r,x,y):
if y < l or r < x:
return Counter()
interval_tree = self.interval_tree
if x<=l and r<=y:
return interval_tree[p]
mid = (l+r)//2
s = Counter()
if x <= mid:
s += self.query(p*2,l,mid,x,y)
if mid <= y:
s += self.query(p*2+1,mid+1,r,x,y)
return Counter(dict(s.most_common(2)))
class MajorityChecker:
def __init__(self, arr: List[int]):
self.n = len(arr)
self.tree = IntervalTree(self.n,arr)
self.tree.build_tree(1,1,self.n)
# print(self.tree.interval_tree)
def query(self, left: int, right: int, threshold: int) -> int:
cnt = self.tree.query(1,1,self.n,left+1,right+1)
ks = [k for k,v in cnt.items() if v >= threshold]
return ks[0] if ks else -1
效率不咋地
二、 493. 翻转对
1. 题目描述
- 翻转对
难度：困难
给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个**重要翻转对**。
你需要返回给定数组中的重要翻转对的数量。
示例 1:
输入: [1,3,2,3,1]
输出: 2
示例 2:
输入: [2,4,3,5,1]
输出: 3
注意:
- 给定数组的长度不会超过
50000。 - 输入数组中的所有数字都在32位整数的表示范围内。
2. 思路分析
这题有点像逆序对。
- 我们可以用树状数组tree维护每个数字出现的次数。
- 倒序遍历，在处理num[i]时，如果tree中存在小于num[i]/2的数据，统计他们出现的个数，就是对num[i]来说组成的
翻转对数量。 - 然后把nums[i]插入树状数组，计数+1。
- 具体实现时，考虑到奇偶性，对每个num,我们需要统计小于等于(num-1)//2的数出现个数。
- 这题数据范围未给出，但是给出了数组长度<=5w，因此需要离散化。
- 需要离散化的数据为nums中所有数据和所有(num-1)//2
3. 代码实现
class BinIndexTree:
def __init__(self, size):
self.size = size
self.bin_tree = [0 for _ in range(size+5)]
def add(self,i,v):
while i<=self.size :
self.bin_tree[i] += v
i += self.lowbit(i)
def update(self,i,v):
val = v - (self.sum(i)-self.sum(i-1))
self.add(i,val)
def sum(self,i):
s = 0
while i >= 1:
s += self.bin_tree[i]
i -= self.lowbit(i)
return s
def lowbit(self,x):
return x&-x
class Solution:
def reversePairs(self, nums: List[int]) -> int:
n = len(nums)
hashed = list(set([(num-1)//2 for num in nums]+nums))
hashed.sort()
size = len(hashed)
tree = BinIndexTree(size)
ans = 0
for i in range(n-1,-1,-1):
num = nums[i]
pos = bisect_left(hashed,num)+1
q = bisect_left(hashed,(num-1)//2)+1
ans += tree.sum(q)
tree.add(pos,1)
return ans