aboutsummaryrefslogtreecommitdiff
path: root/reverse_pairs.py
blob: 3ee2dfe4325a29b3b4de3d8c5ff3dd59b73c2cec (plain)
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
# 493. Reverse Pairs

"""
given an integer array 'nums', return the number of reverse pairs in the
array. a reverse pair is a pair '(i, j)' where '0 <= i < j < nums.len' and
'nums[i] > 2  nums[j]'
"""


class Bits:
    def __init__(self, n):
        self.n = n + 1
        self.sums = [0] * self.n

    def update(self, i, delta):
        while i < self.n:
            self.sums[i] += delta
            i += i & (-i)

    def query(self, i):
        res = 0
        while i > 0:
            res += self.sums[i]
            i -= i & (-i)
        return res


class Solution(object):
    def reversePairs(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        new_nums = nums + [x * 2 for x in nums]
        sorted_set = sorted(list(set(new_nums)))
        tree = Bits(len(sorted_set))
        ans, ranks = 0, {}
        for i, n in enumerate(sorted_set):
            ranks[n] = i + 1
        for n in nums[::-1]:
            ans += tree.query(ranks[n] - 1)
            tree.update(ranks[n * 2], 1)
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(obj.reversePairs(nums=[1, 3, 2, 3, 1]))
    print(obj.reversePairs(nums=[2, 4, 3, 5, 1]))