LeetCode 493. 翻转对

Categories:

题目描述
思路分析
1. 解法一：归并排序计数（推荐）
2. 解法二：树状数组 + 离散化
相似题目

题目描述

✅ 493. 翻转对

思路分析

解法一：归并排序计数（推荐）

核心思路：

在归并排序的分治过程中，左右两段已经有序。

对每个左侧元素 nums[i]，用指针 j 在右侧找到第一个不满足 nums[i] > 2 * nums[j] 的位置。

j 左侧的元素均与 i 构成翻转对，累加数量后再进行归并。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示数组长度。

空间复杂度：O(n)，归并辅助数组。

class Solution {
    public int reversePairs(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        return (int) mergeSort(nums, 0, nums.length - 1);
    }

    private long mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return 0;
        }

        int mid = left + (right - left) / 2;
        long count = 0;

        count += mergeSort(nums, left, mid);
        count += mergeSort(nums, mid + 1, right);

        int j = mid + 1;
        for (int i = left; i <= mid; i++) {
            while (j <= right && (long) nums[i] > 2L * nums[j]) {
                j++;
            }
            count += j - (mid + 1);
        }

        merge(nums, left, mid, right);
        return count;
    }

    private void merge(int[] nums, int left, int mid, int right) {
        int[] tmp = new int[right - left + 1];
        int i = left;
        int j = mid + 1;
        int k = 0;

        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                tmp[k++] = nums[i++];
            } else {
                tmp[k++] = nums[j++];
            }
        }

        while (i <= mid) {
            tmp[k++] = nums[i++];
        }

        while (j <= right) {
            tmp[k++] = nums[j++];
        }

        System.arraycopy(tmp, 0, nums, left, tmp.length);
    }
}

func reversePairs(nums []int) int {
	if len(nums) == 0 {
		return 0
	}

	return int(mergeSort(nums, 0, len(nums)-1))
}

func mergeSort(nums []int, left int, right int) int64 {
	if left >= right {
		return 0
	}

	mid := left + (right-left)/2
	count := int64(0)

	count += mergeSort(nums, left, mid)
	count += mergeSort(nums, mid+1, right)

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

	merge(nums, left, mid, right)
	return count
}

func merge(nums []int, left int, mid int, right int) {
	tmp := make([]int, right-left+1)
	i, j, k := left, mid+1, 0

	for i <= mid && j <= right {
		if nums[i] <= nums[j] {
			tmp[k] = nums[i]
			i++
		} else {
			tmp[k] = nums[j]
			j++
		}
		k++
	}

	for i <= mid {
		tmp[k] = nums[i]
		i++
		k++
	}

	for j <= right {
		tmp[k] = nums[j]
		j++
		k++
	}

	for p := 0; p < len(tmp); p++ {
		nums[left+p] = tmp[p]
	}
}

解法二：树状数组 + 离散化

核心思路：

翻转对条件为 nums[i] > 2 * nums[j] 且 i < j。

从左到右遍历，把已遍历的数加入树状数组。

对当前数 x，查询已出现元素中 <= 2x 的数量，用已出现总数减去该值即为贡献。

为避免溢出与稀疏值，先对 nums[i] 与 2 * nums[i] 做离散化。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示数组长度。

空间复杂度：O(n)，用于离散化数组与树状数组。

class Solution {
    public int reversePairs(int[] nums) {
        List<Long> values = new ArrayList<>();
        for (int num : nums) {
            values.add((long) num);
            values.add(2L * num);
        }

        Collections.sort(values);
        List<Long> uniq = new ArrayList<>();
        for (long v : values) {
            if (uniq.isEmpty() || uniq.get(uniq.size() - 1) != v) {
                uniq.add(v);
            }
        }

        Fenwick tree = new Fenwick(uniq.size());
        long ans = 0;
        long seen = 0;

        for (int num : nums) {
            long target = 2L * num;
            int idx = lowerBound(uniq, target) + 1;
            long leCount = tree.query(idx);

            ans += seen - leCount;

            int pos = lowerBound(uniq, (long) num) + 1;
            tree.add(pos, 1);
            seen++;
        }

        return (int) ans;
    }

    private int lowerBound(List<Long> list, long target) {
        int l = 0;
        int r = list.size();
        while (l < r) {
            int m = l + (r - l) / 2;
            if (list.get(m) >= target) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }

    static class Fenwick {
        private final long[] tree;

        Fenwick(int n) {
            tree = new long[n + 1];
        }

        void add(int idx, long delta) {
            for (int i = idx; i < tree.length; i += i & -i) {
                tree[i] += delta;
            }
        }

        long query(int idx) {
            long sum = 0;
            for (int i = idx; i > 0; i -= i & -i) {
                sum += tree[i];
            }
            return sum;
        }
    }
}

import "sort"

func reversePairs(nums []int) int {
	values := make([]int64, 0, len(nums)*2)
	for _, num := range nums {
		values = append(values, int64(num))
		values = append(values, int64(num)*2)
	}

	sort.Slice(values, func(i, j int) bool {
		return values[i] < values[j]
	})

	uniq := make([]int64, 0, len(values))
	for _, v := range values {
		if len(uniq) == 0 || uniq[len(uniq)-1] != v {
			uniq = append(uniq, v)
		}
	}

	bit := newFenwick(len(uniq))
	ans := int64(0)
	seen := int64(0)

	for _, num := range nums {
		target := int64(num) * 2
		idx := lowerBound(uniq, target) + 1
		leCount := bit.query(idx)

		ans += seen - leCount

		pos := lowerBound(uniq, int64(num)) + 1
		bit.add(pos, 1)
		seen++
	}

	return int(ans)
}

func lowerBound(arr []int64, target int64) int {
	l, r := 0, len(arr)
	for l < r {
		m := l + (r-l)/2
		if arr[m] >= target {
			r = m
		} else {
			l = m + 1
		}
	}
	return l
}

type fenwick struct {
	tree []int64
}

func newFenwick(n int) *fenwick {
	return &fenwick{tree: make([]int64, n+1)}
}

func (f *fenwick) add(idx int, delta int64) {
	for idx < len(f.tree) {
		f.tree[idx] += delta
		idx += idx & -idx
	}
}

func (f *fenwick) query(idx int) int64 {
	sum := int64(0)
	for idx > 0 {
		sum += f.tree[idx]
		idx -= idx & -idx
	}
	return sum
}

相似题目

题目	难度	考察点
315. 计算右侧小于当前元素的个数	困难	归并排序/树状数组
327. 区间和的个数	困难	归并排序
1649. 通过指令创建有序数组	困难	树状数组
775. 全局倒置与局部倒置	中等	逆序对
3159. 查询数组中元素的出现位置	中等	二分/离散化

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/52622596