【算法】Reverse Pairs 翻转对，BIT 解法

@[toc]

题目

Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j].

You need to return the number of important reverse pairs in the given array.

Example1:

Input: [1,3,2,3,1]
Output: 2
Example2:

Input: [2,4,3,5,1]
Output: 3
Note:
The length of the given array will not exceed 50,000.
All the numbers in the input array are in the range of 32-bit integer.

给出一整数数组nums，找出符合 i<j ，同时 nums[i] > 2*nums[j]的数对个数：

1. 数组长度不会超过 50000
2. 所有整数都在 32 位整数范围内

解题思路

本题的条件有两个：

1. i < j
2. nums[i] > num[j] * 2

本题解法用到了 BIT ，有关 BIT 可以到 吃透 Binary Indexed Trees （树状数组）进行了解，不然真心看不懂代码。
本题 BIT 解法基本分为两个重点，一是构造 BIT，二是在 BIT 中计算符合条件的数值个数。

1. 构造 BIT
   1. 构造 BIT 一般需要两个参数，即数值 val 和序号 index
   2. 本题中存在大小比较，所以将 nums 排序后得 copy，而数值在 copy 中的序号index就可以表示大小关系，相同数值取第一个数字的 index 即可
   3. 本题中是求得符合大小比较的数值个数，所以将数值本身插入 BIT 中的没有意义，插入时，将相应节点 +1 即可，还能方便计数
2. 计算符合条件的数值个数
   1. 一般正向的 BIT 中，某节点 i 为含有其本身及向前一共 lowestbit(i) 个节点的和，若要求节点 i 及其之后的和，需要 sum(0,length)-sum(0,i)
   2. 而本题解用的是反向的 BIT，即节点 i 为含有其本身及向后一共 lowestbit(i) 个节点的和，若要求节点 i 及其之后的和，只需要 sum(i,length) 即可

代码实现

Runtime: 1396 ms
Memory Usage: 22.1 MB

func reversePairs(_ nums: [Int]) -> Int {
        return self.BITSolution(nums)
    }
    
    func BITSolution(_ nums: [Int]) -> Int{
        //初始化 res 为0
        var res:Int = 0
        //将数组排序赋予 copy
        let copy:[Int] = nums.sorted(by:<)
        //初始化 BIT ，默认值为0，因为 BIT 是从位置 1 开始的，所以长度要比 nums 多 1
        var bit:[Int] = [Int](repeating:0,count:copy.count + 1)
        //遍历 nums 中的数字
        for ele in nums
        {
            // index 方法获取数字在 copy 的位置，若不存在则会返回大于范围的一个值
            // 在 bit 中返回大于等于 2 * ele + 1 的总数量加值给 res
            res += search(&bit, index(copy, 2 * ele + 1))
            // 由于 copy 是顺序数组，所以 ele 在 copy 中的位置 index 可以代替 ele 本身的价值
            insert(&bit, index(copy, ele))
        }
        //返回结果
        return res
    }
    
    //寻找 val 在 arr中的 index
    func index(_ arr:[Int],_ val:Int) -> Int
    {
        //初始化 l m r，分别表示左序号，中间序号，右序号
        var l:Int = 0
        var r:Int = arr.count - 1
        var m:Int = 0
        //不断循环，直至 l > r
        while(l <= r)
        {
            // m 取 l r 的中间值
            m = l + ((r - l) >> 1)
            //若 arr[m] >= val 将 r = m - 1，缩小区间
            if arr[m] >= val
            {
                r = m - 1
            }
            else
            {
                //否则将 l = m + 1，缩小区间
                l = m + 1
            }
        }
        //遍历结束后，l 即为 val 在 arr 中的 index
        //若不存在时，l 则为超出 arr 范围的值
        //由于 BIT 是从 1 开始的，所以返回值为 l + 1
        return l + 1
    }
    
    // 在 bit 中寻找所有大于 i 的值的个数
    // 由于 bit 中反向存储的 ele 在 copy 中的 index，相同值每次叠加 1，所以将 i 及之后的所有值求和即为结果
    func search(_ bit:inout [Int],_ i:Int) -> Int
    {
        // 将 i 变为可变量
        var i = i
        // 初始化 sum = 0
        var sum:Int = 0
        // 从 i 开始遍历 bit，并将 i 之后的元素加和
        while(i < bit.count)
        {
            sum += bit[i]
            i += i & -i
        }
        // 返回加和后的结果 sum
        return sum
    }
    
    // 在 bit 的位置 i 中将数值 +1
    // 由于需要得知的是符合条件的数值的数量，所以没必要将数值存进去，将相应位置 +1 即可，也能方便计数
    func insert(_ bit:inout [Int],_ i:Int)
    {
        // 将 i 变为可变量
        var i = i
        // 循环将 i 及其影响的父节点对应值 +1
        while(i > 0)
        {
            bit[i] += 1
            i -= i & -i
        }
    }

相关：MergeSort解法
代码地址：https://github.com/sinianshou/EGSwiftLearning