前置知识：归并排序
原理
- 思考一个问题在大范围上的答案，是否等于，左部分的答案 + 右部分的答案 + 跨越左右产生的答案
- 计算“跨越左右产生的答案”时，如果加上左、右各自有序这个设定，会不会获得计算的便利性
- 如果以上两点都成立，那么该问题很可能被归并分治解决（话不说满，因为总有很毒的出题人）
- 求解答案的过程中只需要加入归并排序的过程即可，因为要让左、右各自有序，来获得计算的便利性
题目
小和问题
题目描述
假设数组 s = [ 1, 3, 5, 2, 4, 6]
在s[0]的左边所有 <= s[0]的数的总和为0
在s[1]的左边所有 <= s[1]的数的总和为1
在s[2]的左边所有 <= s[2]的数的总和为4
在s[3]的左边所有 <= s[3]的数的总和为1
在s[4]的左边所有 <= s[4]的数的总和为6
在s[5]的左边所有 <= s[5]的数的总和为15
所以s数组的“小和”为 : 0 + 1 + 4 + 1 + 6 + 15 = 27
给定一个数组arr，实现函数返回arr的“小和”测试链接
答案
package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
const (
MAXN = 1e5 + 1
)
var (
arr = [MAXN]int{}
help = [MAXN]int{}
n int
)
func main() {
input := bufio.NewScanner(os.Stdin)
input.Split(bufio.ScanWords)
out := bufio.NewWriterSize(os.Stdout, 4096)
for input.Scan() {
n, _ = strconv.Atoi(input.Text())
if n == 0 {
continue
}
for i := 0; i < n; i++ {
input.Scan()
arr[i], _ = strconv.Atoi(input.Text())
}
fmt.Fprintln(out, smallSum(0, n-1))
}
out.Flush()
}
func smallSum(left, right int) int {
if left == right {
return 0
}
mid := left + (right-left)>>1
return smallSum(left, mid) + smallSum(mid+1, right) + merge(left, right, mid)
}
func merge(left, right, mid int) int {
sum := 0
l, r, i := left, mid+1, 0
for l <= mid && r <= right {
if arr[r] < arr[l] {
help[i] = arr[r]
r++
} else {
sum += arr[l] * (right - r + 1) // 统计跨越左右的小和
help[i] = arr[l]
l++
}
i++
}
for l <= mid {
help[i] = arr[l]
l++
i++
}
for r <= right {
help[i] = arr[r]
r++
i++
}
copy(arr[left:right+1], help[:right+1-left])
return sum
}翻转对数量
题目描述
给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对
你需要返回给定数组中的重要翻转对的数量
测试链接
答案
var (
theNums []int
)
func reversePairs(nums []int) int {
n := len(nums)
if n == 0 {
return 0
}
theNums = nums
return mergeSort(0, n-1)
}
func mergeSort(left, right int) int {
if left == right {
return 0
}
mid := left + (right-left)>>1
return mergeSort(left, mid) + mergeSort(mid+1, right) + merge(left, right, mid)
}
func merge(left, right, mid int) int {
// 统计部分
count := 0
l, r := left, mid+1
for l <= mid {
for r <= right && theNums[l] > theNums[r]*2 {
r++
}
count += r - mid - 1
l++
}
// 正常merge
l, r, i := left, mid+1, 0
help := make([]int, right-left+1)
for l <= mid && r <= right {
if theNums[r] < theNums[l] {
help[i] = theNums[r]
r++
} else {
help[i] = theNums[l]
l++
}
i++
}
for l <= mid {
help[i] = theNums[l]
l++
i++
}
for r <= right {
help[i] = theNums[r]
r++
i++
}
copy(theNums[left:right+1], help)
return count
}备注
一些用归并分治解决的问题，往往也可以用线段树、树状数组等解法。时间复杂度也都是最优解，这些数据结构都会在【必备】或者【扩展】课程阶段讲到
本节讲述的题目都是归并分治的常规题，难度不大。归并分治不仅可以解决简单问题，还可以解决很多较难的问题，只要符合上面说的特征。比如二维空间里任何两点间的最短距离问题，这个内容会在【挺难】课程阶段里讲述。顶级公司考这个问题的也很少，因为很难，但是这个问题本身并不冷门，来自《算法导论》原题
还有一个常考的算法：“整块分治”。会在【必备】课程阶段讲到
聊：精妙又美丽的思想传统
学习数据结构和算法过程中一定会遇到非常多的思想传统（套路解法、经典思想），不要太过纠结是如何想到的？只要记住这个套路，拿来用即可
要学习、记住、理解这些思想传统，你都不知道有这个思路，更别提如何想到了；只有不断的运用，才会对其理解加深
这些思想传统经过多少前驱者、经过多少岁月的不断完善，才能形成一套解决特定问题的最优思路，我们要做的就是记住再慢慢理解，如果一下就能被你想到了，那你真是天才了！