Golang | Leetcode Golang题解之第493题翻转对

题目：

题解：

type fenwick struct {tree []int
}func newFenwickTree(n int) fenwick {return fenwick{make([]int, n+1)}
}func (f fenwick) add(i int) {for ; i < len(f.tree); i += i & -i {f.tree[i]++}
}func (f fenwick) sum(i int) (res int) {for ; i > 0; i &= i - 1 {res += f.tree[i]}return
}func reversePairs(nums []int) (cnt int) {n := len(nums)if n <= 1 {return}// 离散化所有下面统计时会出现的元素allNums := make([]int, 0, 2*n)for _, v := range nums {allNums = append(allNums, v, 2*v)}sort.Ints(allNums)k := 1kth := map[int]int{allNums[0]: k}for i := 1; i < 2*n; i++ {if allNums[i] != allNums[i-1] {k++kth[allNums[i]] = k}}t := newFenwickTree(k)for i, v := range nums {// 统计之前插入了多少个比 2*v 大的数cnt += i - t.sum(kth[2*v])t.add(kth[v])}return
}