493. Reverse Pairs

题目

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:

1. The length of the given array will not exceed 50,000.
2. All the numbers in the input array are in the range of 32-bit integer.

题目大意

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

注意:

• 给定数组的长度不会超过 50000。
• 输入数组中的所有数字都在 32 位整数的表示范围内。

解题思路

• 给出一个数组，要求找出满足条件的所有的“重要的反转对” (i,j)。重要的反转对的定义是：i<j，并且 nums[i] > 2*nums[j]。
• 这一题是 327 题的变种题。首先将数组中所有的元素以及各自的 2*nums[i] + 1 都放在字典中去重。去重以后再做离散化处理。这一题的测试用例会卡离散化，如果不离散化，Math.MaxInt32 会导致数字溢出，见测试用例中 2147483647, -2147483647 这组测试用例。离散后，映射关系 保存在字典中。从左往右遍历数组，先 query ，再 update ，这个顺序和第 327 题是反的。先 query 查找 [2*nums[i] + 1, len(indexMap)-1] 这个区间内满足条件的值，这个区间内的值都是 > 2*nums[j] 的。这一题移动的是 j，j 不断的变化，往线段树中不断插入的是 i。每轮循环先 query 一次前一轮循环中累积插入线段树中的 i，这些累积在线段树中的代表的是所有在 j 前面的 i。query 查询的是本轮 [2*nums[j] + 1, len(indexMap)-1]，如果能找到，即找到了这样一个 j，能满足 nums[i] > 2*nums[j， 把整个数组都扫完，累加的 query 出来的 count 计数就是最终答案。
• 另外一种解法是树状数组。树状数组最擅长解答逆序对的问题。先将原数组中所有的元素值的 2 倍算出来，和原数组合并到一个大数组中。这个大数组中装了所有可能产生 2 倍逆序对的元素值。然后再将他们所有值排序，离散化。离散化以后便将问题集转化成 [1,N] 这个区间。于是回到了树状数组经典的求逆序对的问题。逆序插入原数组构造树状数组，或者正序插入原数组构造树状数组都可以解答此题。
• 类似的题目：第 327 题，第 315 题。
• 这一题用线段树和树状数组并不是最优解，用线段树和树状数组解这一题是为了训练线段树和树状数组这两个数据结构。最优解是解法一中的 mergesort。

代码

package leetcode

import (
	"sort"

	"github.com/halfrost/leetcode-go/template"
)

// 解法一 归并排序 mergesort，时间复杂度 O(n log n)
func reversePairs(nums []int) int {
	buf := make([]int, len(nums))
	return mergesortCount(nums, buf)
}

func mergesortCount(nums, buf []int) int {
	if len(nums) <= 1 {
		return 0
	}
	mid := (len(nums) - 1) / 2
	cnt := mergesortCount(nums[:mid+1], buf)
	cnt += mergesortCount(nums[mid+1:], buf)
	for i, j := 0, mid+1; i < mid+1; i++ { // Note!!! j is increasing.
		for ; j < len(nums) && nums[i] <= 2*nums[j]; j++ {
		}
		cnt += len(nums) - j
	}
	copy(buf, nums)
	for i, j, k := 0, mid+1, 0; k < len(nums); {
		if j >= len(nums) || i < mid+1 && buf[i] > buf[j] {
			nums[k] = buf[i]
			i++
		} else {
			nums[k] = buf[j]
			j++
		}
		k++
	}
	return cnt
}

// 解法二 树状数组，时间复杂度 O(n log n)
func reversePairs1(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 := 1
	kth := map[int]int{allNums[0]: k}
	for i := 1; i < 2*n; i++ {
		if allNums[i] != allNums[i-1] {
			k++
			kth[allNums[i]] = k
		}
	}
	bit := template.BinaryIndexedTree{}
	bit.Init(k)
	for i, v := range nums {
		cnt += i - bit.Query(kth[2*v])
		bit.Add(kth[v], 1)
	}
	return
}

// 解法三 线段树，时间复杂度 O(n log n)
func reversePairs2(nums []int) int {
	if len(nums) < 2 {
		return 0
	}
	st, numsMap, indexMap, numsArray, res := template.SegmentCountTree{}, make(map[int]int, 0), make(map[int]int, 0), []int{}, 0
	numsMap[nums[0]] = nums[0]
	for _, num := range nums {
		numsMap[num] = num
		numsMap[2*num+1] = 2*num + 1
	}
	// numsArray 是 prefixSum 去重之后的版本，利用 numsMap 去重
	for _, v := range numsMap {
		numsArray = append(numsArray, v)
	}
	// 排序是为了使得线段树中的区间 left <= right，如果此处不排序，线段树中的区间有很多不合法。
	sort.Ints(numsArray)
	// 离散化，构建映射关系
	for i, n := range numsArray {
		indexMap[n] = i
	}
	numsArray = []int{}
	// 离散化，此题如果不离散化，MaxInt32 的数据会使得数字越界。
	for i := 0; i < len(indexMap); i++ {
		numsArray = append(numsArray, i)
	}
	// 初始化线段树，节点内的值都赋值为 0，即计数为 0
	st.Init(numsArray, func(i, j int) int {
		return 0
	})
	for _, num := range nums {
		res += st.Query(indexMap[num*2+1], len(indexMap)-1)
		st.UpdateCount(indexMap[num])
	}
	return res
}

---