第五周 二分、排序

题目数：20

本周作业

• 1011.在 D 天内送达包裹的能力 重点

（Medium）半年内出题频次：

// 官方题解：
func shipWithinDays(weights []int, D int) int {
    // 确定二分查找左右边界
    left, right := 0, 0
    for _, w := range weights {
        if w > left {
            left = w
        }
        right += w
    }
    return left + sort.Search(right-left, func(x int) bool {
        x += left
        day := 1 // 需要运送的天数
        sum := 0 // 当前这一天已经运送的包裹重量之和
        for _, w := range weights {
            if sum+w > x {
                day++
                sum = 0
            }
            sum += w
        }
        return day <= D
    })
}
// 官方c++版本go化
func shipWithinDays(weights []int, days int) int {
    left, right := weights[0], weights[0]
    for _, weight := range weights[1:] {
        if weight > left {
            left = weight 
        }
        right += weight
    }
    for left < right {
        mid := (left + right) >> 1
        need, cur := 1, 0
        for _, weight := range weights {
            if cur + weight > mid {
                cur = 0
                need++
            }
            cur += weight
        }
        if need <= days {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

// 训练营
func shipWithinDays(weights []int, days int) int {
    low, high := weights[0], weights[0]
    for _, weight := range weights[1:] {
        if weight > low {
            low = weight 
        }
        high += weight
    }
    for low < high {
        mid := (low + high) >> 1
        if validate(weights, mid, days) {
            high = mid
        } else {
            low = mid + 1
        }
    }
    return low
}

func validate(weights []int, weight, day int) bool {
    cur, curDay := 0, 1 // 注意curDay初始化为1
    for _, w := range weights {
        if cur + w <= weight {
            cur += w
        } else {
            curDay++
            cur = w
        }
    }
    return curDay <= day
}

• 911.在线选举 重点

（Medium） 1 年内出题频次：

type TopVotedCandidate struct {
    tops, times []int
}

func Constructor(persons, times []int) TopVotedCandidate {
    tops := []int{}
    top := -1
    voteCounts := map[int]int{-1: -1}
    for _, p := range persons {
        voteCounts[p]++
        if voteCounts[p] >= voteCounts[top] {
            top = p
        }
        tops = append(tops, top)
    }
    return TopVotedCandidate{tops, times}
}

func (c *TopVotedCandidate) Q(t int) int {
    return c.tops[sort.SearchInts(c.times, t+1)-1]
}


/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * obj := Constructor(persons, times);
 * param_1 := obj.Q(t);
 */

class TopVotedCandidate {
    List<Integer> tops;
    Map<Integer, Integer> voteCounts;
    int[] times;

    public TopVotedCandidate(int[] persons, int[] times) {
        tops = new ArrayList<Integer>();
        voteCounts = new HashMap<Integer, Integer>();
        voteCounts.put(-1, -1);
        int top = -1;
        for (int i = 0; i < persons.length; ++i) {
            int p = persons[i];
            voteCounts.put(p, voteCounts.getOrDefault(p, 0) + 1);
            if (voteCounts.get(p) >= voteCounts.get(top)) {
                top = p;
            }
            tops.add(top);
        }
        this.times = times;
    }
    
    public int q(int t) {
        int l = 0, r = times.length - 1;
        // 找到满足 times[l] <= t 的最大的 l
        while (l < r) {
            int m = l + (r - l + 1) / 2;
            if (times[m] <= t) {
                l = m;
            } else {
                r = m - 1;
            }
        }
        return tops.get(l);
    }
}

• 875.爱吃香蕉的珂珂 重点

（Medium）半年内出题频次：

func minEatingSpeed(piles []int, h int) int {
    low, high := 1, int(1e9)
    for low < high {
        mid := low + (high - low) >> 1
        if validate(piles, h, mid) {
            high = mid
        } else {
            low = mid + 1
        }
    }
    return low
}

func validate(piles []int, h int, k int) bool {
    time := 0
    for _, pile := range piles {
        // 向上取整
        time += (pile - 1) / k + 1 // (pile + k - 1) / k
    }
    return time <= h
}

• 372.区间和的个数（选做） 重点 重点

（Hard）半年内出题频次：

// 方法一：归并排序
func countRangeSum(nums []int, lower int, upper int) (ans int) {
    var mergeSort func([]int, int, int)
    mergeSort = func(preSum []int, left, right int) {
        if left >= right {
            return
        }
        mid := (left + right) >> 1
        mergeSort(preSum, left, mid)
        mergeSort(preSum, mid + 1, right)
        // 计算统计
        l, r := mid + 1, mid + 1
        for i := left; i <= mid; i++ {
            for l <= right && preSum[l] - preSum[i] < lower {
                l++
            }
            for r <= right && preSum[r] - preSum[i] <= upper {
                r++
            }
            ans += r - l
        }

        // 合并
        tmp := make([]int, right - left + 1)
        i, j := left, mid + 1
        for k := 0; k < len(tmp); k++ {
            if j > right || (i <= mid && preSum[i] <= preSum[j]) {
                tmp[k], i = preSum[i], i + 1
            } else {
                tmp[k], j = preSum[j], j + 1
            }
        }
        for i, v := range tmp {
            preSum[left+i] = v
        }
    }
    preSum := make([]int, len(nums) + 1)
    for i, num := range nums {
        preSum[i+1] = preSum[i] + num
    }
    mergeSort(preSum, 0, len(preSum)-1)
    return ans
}
// 归并官方写法
func countRangeSum(nums []int, lower, upper int) int {
    var mergeCount func([]int) int
    mergeCount = func(arr []int) int {
        n := len(arr)
        if n <= 1 {
            return 0
        }

        n1 := append([]int(nil), arr[:n/2]...)
        n2 := append([]int(nil), arr[n/2:]...)
        cnt := mergeCount(n1) + mergeCount(n2) // 递归完毕后，n1 和 n2 均为有序

        // 统计下标对的数量
        l, r := 0, 0
        for _, v := range n1 {
            for l < len(n2) && n2[l]-v < lower {
                l++
            }
            for r < len(n2) && n2[r]-v <= upper {
                r++
            }
            cnt += r - l
        }

        // n1 和 n2 归并填入 arr
        p1, p2 := 0, 0
        for i := range arr {
            if p1 < len(n1) && (p2 == len(n2) || n1[p1] <= n2[p2]) {
                arr[i] = n1[p1]
                p1++
            } else {
                arr[i] = n2[p2]
                p2++
            }
        }
        return cnt
    }

    prefixSum := make([]int, len(nums)+1)
    for i, v := range nums {
        prefixSum[i+1] = prefixSum[i] + v
    }
    return mergeCount(prefixSum)
}
// 方法二：线段树

// 方法三：动态增加节点的线段树

// 方法四：树状数组

// 方法五：平衡二叉搜索树

class Solution {
    public int countRangeSum(int[] nums, int lower, int upper) {
        long s = 0;
        long[] sum = new long[nums.length + 1];
        for (int i = 0; i < nums.length; ++i) {
            s += nums[i];
            sum[i + 1] = s;
        }
        return countRangeSumRecursive(sum, lower, upper, 0, sum.length - 1);
    }

    public int countRangeSumRecursive(long[] sum, int lower, int upper, int left, int right) {
        if (left == right) {
            return 0;
        } else {
            int mid = (left + right) / 2;
            int n1 = countRangeSumRecursive(sum, lower, upper, left, mid);
            int n2 = countRangeSumRecursive(sum, lower, upper, mid + 1, right);
            int ret = n1 + n2;

            // 首先统计下标对的数量
            int i = left;
            int l = mid + 1;
            int r = mid + 1;
            while (i <= mid) {
                while (l <= right && sum[l] - sum[i] < lower) {
                    l++;
                }
                while (r <= right && sum[r] - sum[i] <= upper) {
                    r++;
                }
                ret += r - l;
                i++;
            }

            // 随后合并两个排序数组
            long[] sorted = new long[right - left + 1];
            int p1 = left, p2 = mid + 1;
            int p = 0;
            while (p1 <= mid || p2 <= right) {
                if (p1 > mid) {
                    sorted[p++] = sum[p2++];
                } else if (p2 > right) {
                    sorted[p++] = sum[p1++];
                } else {
                    if (sum[p1] < sum[p2]) {
                        sorted[p++] = sum[p1++];
                    } else {
                        sorted[p++] = sum[p2++];
                    }
                }
            }
            for (int j = 0; j < sorted.length; j++) {
                sum[left + j] = sorted[j];
            }
            return ret;
        }
    }
}

• 154.寻找旋转排序数组中的最小值 II 重点

重点（Hard）半年内出题频次：

// 数组中存在重复值
func findMin(nums []int) int {
    low, high := 0, len(nums)-1
    for low < high {
        mid := low + (high - low) >> 1
        if nums[mid] < nums[high] {
            high = mid
        } else if nums[mid] > nums[high] {
            low = mid + 1
        } else {
            high-- // nums[mid] == nums[high] 相等，逐渐缩小high
        }
    }
    return nums[low] // 返回 nums[high] 也可
}

• 74.搜索二维矩阵 （Medium）半年内出题频次：

func searchMatrix(matrix [][]int, target int) bool {
    n := len(matrix[0])
    left, right := 0, len(matrix) * len(matrix[0]) - 1
    for left <= right {
        mid := (left + right) >> 1
        row, col := mid/n, mid%n
        if matrix[row][col] == target {
            return true
        } else if matrix[row][col] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return false
}

实战例题

以下为课上实战例题

第 9 课 二分

二分查找

• 704.二分查找 （Easy）半年内出题频次：

func search(nums []int, target int) int {
    left, right := 0, len(nums) - 1
    for left <= right {
        mid := left + (right - left) >> 1
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

• 153.寻找旋转排序数组中的最小值 （Medium）半年内出题频次：

/*
3 4 5 1 2 让每个数尝试给结尾数比较 nums[i] <= nums[n-1]
0 0 0 1 1
*/
func findMin(nums []int) int {
    left, right := 0, len(nums) - 1
    for left < right {
        mid := left + (right - left) >> 1
        // 条件满足true， 即为1
        if nums[mid] <= nums[right] {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return nums[right]
}

// 以前的垃圾写法
func findMin(nums []int) int {
    l, r := 0, len(nums) - 1
    if nums[l] < nums[r] || r == l {
        return nums[l]
    }
    for l < r {
        m := l + (r - l) >> 1
        if nums[m] > nums[m + 1] {
            return nums[m + 1]
        }
        if nums[m - 1] > nums[m] {
            return nums[m]
        }
        if nums[0] < nums[m] {
            l = m + 1
        } else {
            r = m - 1
        }
    }
    return nums[0]
}

• 34.在排序数组中查找元素的第一个和最后一个位置 （Medium）半年内出题频次：

// 训练营
func searchRange(nums []int, target int) []int {
    ans := make([]int, 2)
    // 查找 第一个 >=target 的位置
    left, right := 0, len(nums)
    for left < right {
        mid := (left + right) >> 1
        if nums[mid] >= target {
            right = mid
        } else {
            left = mid + 1
        }
    }
    ans[0] = right
    // 查找 最后一个 <=target 的位置
    left, right = -1, len(nums) - 1
    for left < right {
        mid := (left + right + 1) >> 1
        if nums[mid] <= target {
            left = mid
        } else {
            right = mid - 1
        }
    }
    ans[1] = right
    if ans[0] > ans[1] {
        return []int{-1, -1}
    }
    return ans
}
// 以前写法
func searchRange(nums []int, target int) []int {
    leftmost := sort.SearchInts(nums, target)
    if leftmost == len(nums) || nums[leftmost] != target {
        return []int{-1, -1}
    }
    rightmost := sort.SearchInts(nums, target + 1) - 1
    return []int{leftmost, rightmost}
}

• 69.Sqrt(x) （Easy）半年内出题频次：

// 训练营写法一
func mySqrt(x int) int {
    left, right := 1, x
    for left < right {
        mid := (left + right + 1) >> 1
        if mid * mid <= x {
            left = mid
        } else {
            right = mid - 1
        }
    }
    return right
}
// 训练营写法二
func mySqrt(x int) int {
    left, right := 1, x
    for left < right {
        mid := (left + right + 1) >> 1
        if mid <= x / mid {
            left = mid
        } else {
            right = mid - 1
        }
    }
    return right
}
// 训练营写法三
func mySqrt(x int) int {
    return int(myRealSqrt(float64(x)))
}
func myRealSqrt(x float64) float64 {
    left, right := float64(0), x
    for right - left > 1e-7 {
        mid := (right + left) / 2
        if mid * mid <= x {
            left = mid
        } else {
            right = mid
        }
    }
    return right
}

// 训练营写法三
class Solution {
    public int mySqrt(int x) {
        return (int)myRealSqrt(x);
    }

    public double myRealSqrt(double x) {
        double left = 0, right = x;
        while (right - left > 1e-7) {
            double mid = (left + right) / 2;
            if (mid * mid <= x) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return right;
    }
}

三分查找

• 162.寻找峰值 重点

（Medium）半年内出题频次：

func findPeakElement(nums []int) int {
    left, right := 0, len(nums) - 1
    for left < right {
        mid := (left + right) >> 1
        if nums[mid] <= nums[mid+1] {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return right
}
// 训练营写法
func findPeakElement(nums []int) int {
    left, right := 0, len(nums) - 1
    for left < right {
        lmid := (left + right) >> 1
        rmid := lmid + 1
        if nums[lmid] <= nums[rmid] {
            left = lmid + 1
        } else {
            right = rmid - 1
        }
    }
    return right
}

二分答案

• 374.猜数字大小 （Easy）半年内出题频次：

/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is lower than the guess number
 *			      1 if num is higher than the guess number
 *               otherwise return 0
 * func guess(num int) int;
 */
// 训练营写法
func guessNumber(n int) int {
    left, right := 0, n
    for left < right {
        mid := (left + right) >> 1
        if guess(mid) <= 0 {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return right
}
// 自己
func guessNumber(n int) int {
    left, right := 1, n
    for left <= right {
        mid := (left+right) >> 1
        pick := guess(mid)
        if pick == 0 {
            return mid
        } else if pick == -1 {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return right
}
// 官方题解
func guessNumber(n int) int {
    return sort.Search(n, func(x int) bool { return guess(x) <= 0 })
}

• 410.分割数组的最大值 重点

（Hard）半年内出题频次：

// 训练营
func splitArray(nums []int, m int) int {
    left, right := 0, 0
    for _, num := range nums {
        right += num
        if left < num {
            left = num
        }
    }
    for left < right {
        mid := (left + right) >> 1
        if validate(nums, m, mid) {
            right = mid
        } else {
            left = mid+1
        }
    }
    return right
}

func validate(nums[]int, m, size int) bool {
    count, box := 1, 0
    for _, num := range nums {
        if box + num <= size {
            box += num
        } else {
            box = num
            count++
        }
    }
    return count <= m
}

• 1482.制作 m 束花所需的最少天数 重点

（Medium） 2 年内出过此题：

// 训练营
func minDays(bloomDay []int, m int, k int) int {
    left, latestBloom := 0, 0
    for _, bloom := range bloomDay {
        if latestBloom < bloom {
            latestBloom = bloom
        }
    }
    right := latestBloom + 1
    for left < right {
        mid := (left + right) >> 1
        if validate(bloomDay, m, k, mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    if right == latestBloom + 1 {
        return -1
    }
    return right
}

func validate(bloomDay []int, m, k int, now int) bool {
    bouquet, consecutine := 0, 0
    for _, bloom := range bloomDay {
        if bloom <= now {
            consecutine++
            if bouquet == k {
                bouquet = 0
                bouquet++
            }
        } else {
            consecutine = 0
        }
    }
    return bouquet >= m
}

第 10 课 排序

排序

• 912.排序数组 重点

（Medium）半年内出题频次：

// todo: 练习10中排序

• 数组的相对排序 重点

（Easy）半年内出题频次：

// 方法一：排序
func relativeSortArray(arr1 []int, arr2 []int) []int {
    mp := make(map[int]int, len(arr2))
    for i, num := range arr2 {
        mp[num] = i
    }
    sort.Slice(arr1, func(i, j int) bool {
        x, xo := mp[arr1[i]]
        if !xo {
            x = len(arr1)
        }
        y, yo := mp[arr1[j]]
        if !yo  {
            y = len(arr1)
        }
        return x < y || (x == y && arr1[i] < arr1[j])
    })
    return arr1
}
// 方法二：计数
// https://leetcode-cn.com/submissions/detail/261393931/
// https://leetcode-cn.com/submissions/detail/123303531/
func relativeSortArray(arr1 []int, arr2 []int) (ans []int) {
   cnt := make([]int, 10001)
   for _, v := range arr1 {
       cnt[v]++
   }
   for _, v := range arr2 {
       for cnt[v] > 0 {
           ans = append(ans, v)
           cnt[v]--
       }
   }
   for v := range cnt {
       for cnt[v] > 0 {
           ans = append(ans, v)
           cnt[v]--
       }
   }
   return ans
}

• 合并区间 重点

（Medium）半年内出题频次：

// 写法一：
func merge(intervals [][]int) (ans [][]int) {
    if len(intervals) <= 1 {
		return intervals
	}
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0] || (intervals[i][0] == intervals[j][0] && intervals[i][1] < intervals[j][1])
    })
    // 其他提交记录，均为下面写法不同
    cur := intervals[0]
    for i := 1; i < len(intervals); i++ {
        if cur[1] >= intervals[i][0] {
            cur[1] = max(cur[1], intervals[i][1])
        } else {
            ans = append(ans, cur)
            cur = intervals[i]
        }
    }
    ans = append(ans, cur)
    return ans
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
// 写法二：
func merge(intervals [][]int) (res [][]int) {
	if len(intervals) <= 1 {
		return intervals
	}

	// 第一个数字升序
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})

	left, right := intervals[0][0], intervals[0][1]
	for i := 1; i < len(intervals); i++ {
		if right >= intervals[i][0] {
			// 有交叉
			right = max(right, intervals[i][1])
		} else {
			res = append(res, []int{left, right})
			left, right = intervals[i][0], intervals[i][1]
		}
	}
	res = append(res, []int{left, right})

	return res
}

// 训练营：go翻译版本
func merge(intervals [][]int) (ans [][]int) {
    if len(intervals) <= 1 {
		return intervals
	}
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0] || (intervals[i][0] == intervals[j][0] && intervals[i][1] < intervals[j][1])
    })
    start, end := -1, -1
    for _, interval := range intervals {
        left, right := interval[0], interval[1]
        if left <= end {
            end = max(end, right)
        } else {
            if end != -1 {
                ans = append(ans, []int{start, end})
            }
            start = left
            end = right
        }
    }
    ans = append(ans, []int{start, end})
    return ans
}

// 训练营解法一

// 训练营解法二
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<pair<int, int>> events;
        for (const vector<int> &interval : intervals) {
            events.push_back({interval[0], 1});
            events.push_back({interval[1] + 1, -1});
        }
        sort(events.begin(), events.end());
        int covering = 0;
        int start;
        vector<vector<int>> ans;
        for (const pair<int, int>& event : events) {
            if (covering == 0) start = event.first;
            covering += event.second;
            if (covering == 0) {
                ans.push_back({start, event.first - 1});
            }
        }
        return ans;
    }
};

• 数组中的第 K 个最大元素 重点

（Medium）半年内出题频次：

// 最佳解法：利用快排
func findKthLargest(nums []int, k int) int {
    return quickSort(nums, 0, len(nums) - 1, len(nums) - k)
}

func quickSort(nums []int, left, right, idx int) int {
    if left >= right {
        return nums[left]
    }
    pivot := partition(nums, left, right)
    if idx <= pivot {
        return quickSort(nums, left, pivot, idx)
    } else {
        return quickSort(nums, pivot + 1, right, idx)
    }
}

func partition(nums []int, l, r int) int {
    pivot := l + (r - l) >> 1
    pivotVal := nums[pivot]
    for l <= r {
        for nums[l] < pivotVal {l++}
        for pivotVal < nums[r] {r--}
        if l == r {
            break
        }
        if l < r {
            nums[l], nums[r] = nums[r], nums[l]
            l++
            r--
        }
    }
    return r
}

// 训练营
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        return quickSort(nums, 0, nums.size()-1, nums.size()-k);
    }
private:
    int quickSort(vector<int>& nums, int l, int r, int index) {
        if (l >= r) {
            return nums[l];
        }
        int pivot = partition(nums, l, r);
        if (index <= pivot) {
            return quickSort(nums, l, pivot, index);
        } else {
            return quickSort(nums, pivot + 1, r, index);
        }
    }
    int partition(vector<int>& nums, int l, int r) {
        int pivot = l + rand() % (r - l + 1);
        int pivotVal = nums[pivot];
        while (l <= r) {
            while (nums[l] < pivotVal) l++;
            while (nums[r] > pivotVal) r--;
            if (l == r) break;
            if (l < r) {
                int tmp = nums[l];
                nums[l] = nums[r];
                nums[r] = tmp;
                l++; r--;
            }
        }
        return r;
    }
};
// 方法二：最小堆
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
      //最小堆
      std::priority_queue<int, std::vector<int>, std::greater<int>> Q;
      //遍历nums数组
      for (int i = 0; i < nums.size(); i++){
        if (Q.size() < k) {
          Q.push(nums[i]);
        } else if (nums[i] > Q.top()) {
          Q.pop();
          Q.push(nums[i]);
        }
      }
      return Q.top();//返回堆顶
    }
};

• 104.货仓选址 （Easy）（ACWing）

// 训练营写法，排序取中位数，在迭代计算
#include<bits/stdc++.h>
using namespace std;

int a[100000];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    sort(a, a + n);
    int pos = a[n / 2];
    int ans = 0;
    for (int i = 0; i < n; i++)  ans += abs(pos - a[i]);
    cout << ans << endl;
}

• 493.翻转对 重点

（Hard）半年内出题频次：

// 官方其他解法：树状数组，（参考 327. 区间和的个数 官方题解更多解法）
// 训练营写法
func reversePairs(nums []int) (ans int) {
	mergeSort(nums, 0, len(nums)-1, &ans)
	return ans
}

func mergeSort(nums []int, left, right int, count *int) {
	if left >= right {
		return
	}
	mid := left + (right - left) >> 1
	mergeSort(nums, left, mid, count)
	mergeSort(nums, mid + 1, right, count)
	counter(nums, left, mid , right, count)
	merge(nums, left, mid, right)
}

func counter(nums []int, left, mid, right int, count *int) {
	j := mid + 1 // j := mid 
	for i := left; i <= mid; i++ {
		for j <= right && nums[i] > 2 * nums[j] { // for j <= right && nums[i] > 2 * nums[j + 1] {
			j++
		}
		*count += j - mid - 1 // *count += j - mid
	}
}

func merge(nums []int, left, mid, right int)  {
	tmp := make([]int, right - left + 1)
	i, j := left, mid + 1
	for k := 0; k < len(tmp); k++ {
		if j > right || (i <= mid && nums[i] <= nums[j]) {
			tmp[k], i = nums[i], i + 1
		} else {
			tmp[k], j = nums[j], j + 1
		}
	}
	for k, v := range tmp {
		nums[left+k] = v
	}
}

简化归并：https://leetcode-cn.com/submissions/detail/261660445/

func reversePairs(nums []int) int {
    return mergeSort(nums, 0, len(nums) - 1)
}

func mergeSort(nums []int, left int, right int) int {
   if left >= right {
        return 0
    }
    mid := left + (right - left) >> 1
    cnt := mergeSort(nums, left, mid) + mergeSort(nums, mid + 1, right)
    // 计算翻转对，并归并
    cache := make([]int, right - left + 1)
    c, i, l := 0, left, left
    for j := mid + 1; j <= right; j, c = j + 1, c + 1 {
        for i <= mid && nums[i] <= nums[j] * 2 {
            i++
        }
        for ; l <= mid && nums[l] < nums[j]; l, c = l + 1, c + 1 {
            cache[c] = nums[l]
        }
        cache[c] = nums[j]
        cnt += mid - i + 1 // i -> mid 是 ok 的
    }
    for ; l <= mid; l, c = l + 1, c + 1 {
        cache[c] = nums[l]
    }
    // 合并
    for i, n := 0, right - left + 1; i < n; i++ {
        nums[left + i] = cache[i]
    }
    return cnt
}

标准归并：https://leetcode-cn.com/submissions/detail/261652038/

// 使用归并排序统计
func reversePairs(nums []int) int {
    res := make([]int,len(nums))
    count := 0
    mergeSort(nums, res, 0, len(res)-1, &count)
    return count
}

func mergeSort(nums, res []int, start, end int, count *int)  {
    if start >= end {
        return 
    }

    mid := start + (end - start) >> 1
    mergeSort(nums, res, start, mid, count)
    mergeSort(nums, res, mid+1, end, count)
    counter(nums, start, end, count)
    merge(nums, res, start, end)
}

func counter(nums []int, start, end int, count *int) {
    mid := start + (end - start) >> 1
    l1, l2 := start, mid + 1
    for l1 <= mid && l2 <= end {
        if nums[l1] > 2 * nums[l2] {
            *count += mid - l1 + 1
            l2++
        } else {
            l1++
        }
    }
}

func merge(nums, res []int,start,end int) {
    //遍历指针
    mid := start + (end - start) >> 1
    index1,index2 := start, mid+1
    t := start
    for index1 <= mid && index2 <= end{
        if nums[index1] <= nums[index2]{
            res[t] = nums[index1]
            index1++; t++
        }else{
            res[t] = nums[index2]
            index2++; t++
            //此时右边的数小于左边的数，记录逆序对
        }
    }
    // 补全剩余的数字
    for index1 <= mid{
        res[t] = nums[index1]
        index1++; t++
    }
    for index2 <= end {
        res[t] = nums[index2]
        index2++; t++
    }

    for start <= end {
        nums[start] = res[start]
        start++
    }
}

官方简化归并：https://leetcode-cn.com/submissions/detail/126933753/

func reversePairs(nums []int) int {
    n := len(nums)
    if n <= 1 {
        return 0
    }

    n1 := append([]int(nil), nums[:n/2]...)
    n2 := append([]int(nil), nums[n/2:]...)
    cnt := reversePairs(n1) + reversePairs(n2) // 递归完毕后，n1 和 n2 均为有序

    // 统计重要翻转对 (i,j) 的数量
    // 由于 n1 和 n2 均为有序，可以用两个指针同时遍历
    j := 0
    for _, v := range n1 {
        for j < len(n2) && v > 2*n2[j] {
            j++
        }
        cnt += j
    }

    // n1 和 n2 归并填入 nums
    p1, p2 := 0, 0
    for i := range nums {
        if p1 < len(n1) && (p2 == len(n2) || n1[p1] <= n2[p2]) {
            nums[i] = n1[p1]
            p1++
        } else {
            nums[i] = n2[p2]
            p2++
        }
    }
    return cnt
}