并归排序的应用 I

LARRY1024 / 2024-01-27 / 原文

1. 题目列表
2. 应用
- 2.1. Leetcode 315. 计算右侧小于当前元素的个数
  - 2.1.1. 题目
  - 2.1.2. 解题思路
  - 2.1.3. 代码实现

1. 题目列表

题目列表：

序号	题目	难度
1	315. 计算右侧小于当前元素的个数	困难

2. 应用

2.1. Leetcode 315. 计算右侧小于当前元素的个数

2.1.1. 题目

315. 计算右侧小于当前元素的个数

给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例 1：

输入：nums = [5,2,6,1]
输出：[2,1,1,0]
解释：

5 的右侧有 2 个更小的元素 (2 和 1)

2 的右侧仅有 1 个更小的元素 (1)

6 的右侧有 1 个更小的元素 (1)

1 的右侧有 0 个更小的元素

2.1.2. 解题思路

首先，我们需要定义一个数据结构 (int value, int index) 来记录每一个元素以及它在数组 $nums$ 中的索引。

这样，我们可以将原始数组，转换成新的数组 $array$ ，其中，$array$ 中的每一个元素都记录了值和索引。

同时，我们需要一个数组 $count$ 用于记录每一个位置比它小的元素个数。

这里，我们需要借助并归排序的思想，在合并两个有序数组的时候，记录每一个元素右侧比它小的元素个数。

这里，我们以合并两个子数组 $[1,3,5]$、$[2,4,6,,7]$ 为例来描述查找过程：

当我们依次合并两个数组时，当某一个时刻，应该合并 $temp[i] = 5$ 的时候，可以看出，在原始数组 $nums$ 中，比 $5$ 小的元素，就是索引 $j$ 和索引 $mid + 1$ 的距离，即 2 个。

也就是说，在对 $nuns[left \cdots right]$ 合并的过程中，每当执行 $nums[k] = temp[i]$ 时，就可以确定 $temp[i]$ 这个元素后面比它小的元素个数为 $j - mid - 1$。

2.1.3. 代码实现

class Solution {
    private class Pair {
        int val, id;
        Pair(int val, int id) {
            this.val = val;
            this.id = id;
        }
    }

    private Pair[] temp;

    private int[] count;

    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        count = new int[n];
        temp = new Pair[n];
        Pair[] array = new Pair[n];
        for (int i = 0; i < n; i++) {
            array[i] = new Pair(nums[i], i);
        }

        sort(array, 0, n - 1);

        List<Integer> result = new LinkedList<>();
        for (int c : count) {
            result.add(c);
        }
        return result;
    }

    private void sort(Pair[] array, int left, int right) {
        if (left == right) {
            return;
        }

        int mid = left + (right - left) / 2;
        sort(array, left, mid);
        sort(array, mid + 1, right);
        merge(array, left, mid, right);
    }

    private void merge(Pair[] array, int left, int mid, int right) {
        for (int i = left; i <= right; i++) {
            temp[i] = array[i];
        }

        int i = left, j = mid + 1, k = left;
        while (i <= mid && j <= right) {
            if (temp[i].val > temp[j].val) {
                array[k] = temp[j++];
            } else {
                array[k] = temp[i++];
                count[array[k].id] += j - mid - 1;
            }
            k++;
        }

        while (i <= mid) {
            array[k] = temp[i++];
            count[array[k].id] += j - mid - 1;
            k++;
        }

        while (j <= right) {
            array[k++] = temp[j++];
        }
    }
}

参考：