[英雄星球六月集训LeetCode解题日报] 第15日 树状数组

日报

• 第一题不会用树状数组，写个线段树吧。
• 第二题有点像逆序对。

题目

一、 1157. 子数组中占绝大多数的元素

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    
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

效率不咋地

二、 493. 翻转对

493. 翻转对

1. 题目描述

493. 翻转对

难度：困难

给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个**重要翻转对**。

你需要返回给定数组中的重要翻转对的数量。

示例 1:

输入: [1,3,2,3,1]
输出: 2

1
2
3

示例 2:

输入: [2,4,3,5,1]
输出: 3

1
2
3

注意:

1. 给定数组的长度不会超过50000。
2. 输入数组中的所有数字都在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
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

参考链接

• 链接: [python刷题模板] 树状数组