0493. Reverse Pairs

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] 的。这一题移动的是 jj 不断的变化,往线段树中不断插入的是 i。每轮循环先 query 一次前一轮循环中累积插入线段树中的 i,这些累积在线段树中的代表的是所有在 j 前面的 i。query 查询的是本轮 [2*nums[j] + 1, len(indexMap)-1],如果能找到,即找到了这样一个 j,能满足 nums[i] > 2*nums[j, 把整个数组都扫完,累加的 query 出来的 count 计数就是最终答案。
  • 类似的题目:第 327 题,第 315 题。
  • 这一题用线段树并不是最优解,用线段树解这一题是为了训练线段树这个数据结构。最优解是解法二中的 mergesort。

代码 #


package leetcode

import (
	"sort"

	"github.com/halfrost/LeetCode-Go/template"
)

// 解法一 线段树,时间复杂度 O(n log n)
func reversePairs(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
}

// 解法二 mergesort
func reversePairs1(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
}


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者