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

题目描述

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

示例一：

输入: [5,2,6,1]
输出: [2,1,1,0] 
解释:
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
1 的右侧有 0 个更小的元素.

题解

二分查找

这道题目要想到二分查找的一个性质: 在一个排序数组中, 可以通过二分查找目标值的左边界来表示数组中有多少个元素小于目标值

比如一个数组为:[1, 2, 2, 4, 5, 6], 查找数字4的返回值是3, 结果不言而喻.

那么我们需要想办法创造出排序数组的条件.

首先初始化一个空的列表用于存放遍历后的元素, 因为这道题目是考察右侧有多少个更小的元素, 所以要从右往左遍历, 这能保证每遍历到一个元素, 列表中的元素都位于它的右边, 只需要在它们之间查找即可.

二分查找的结果即为元素右边有多少更小的值, 并将其插入到合适的位置使列表仍然是有序的.

public List<Integer> countSmaller(int[] nums) {
        LinkedList<Integer> res = new LinkedList<>();
        List<Integer> list = new ArrayList<>();

        for (int i = nums.length - 1; i >= 0; i--) {
            res.addFirst(binarySearch(list, nums[i]));
            list.add(binarySearch(list, nums[i]), nums[i]);
        }
        return res;

    }

    public int binarySearch(List<Integer> list, int target) {
        int left = 0;
        int right = list.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (list.get(mid) >= target) right = mid - 1;
            else if (list.get(mid) < target) left = mid + 1;
        }
        return left;
    }

在做这道题时因为要用到向列表中某个位置插入元素, 找响应的insert() 方法, 怎么也找不到, 原来直接用add() 方法就好了, 如果只填一个元素, 默认为列表尾部添加元素, 如果在前面写上索引, 即为在指定位置插入元素, 剩余元素后移.

归并排序(重点!!)

如果使用归并排序的方法, 与剑指OFFER 51题.数组中的逆序对的思路类似, 都是在并的过程中记录大小, 然而这道题更为复杂, 需要考虑的难点更多, 首先来总结两道题在关键步骤, 也就是排序时的共同思路:

共同思路

假设当前有两个已排好序的数组,

• 如果要求逆序对数量, 如果左边数列中有数字比右边的数字大, 那么就存在逆序对, 当开始从右边的序列中挑选数字时, 说明当前左右序列的首个数字中右边的数字更小, 又由于两个序列都是有序的, 也就是说当前左边序列中有mid - i +1个数字都是比右边这个数字大, 所以右边这个数字贡献了mid - i +1个逆序对
• 如果要求的是右侧小于当前元素的个数, 因为每次都要选取左右两序列中较小的头元素加入排序后的序列, 所以每当要添加左序列的头元素时, 已经添加的右侧序列的元素都是比它小的数, 所以就等于r - mid + 1

拓展点

• 逆序对的问题是累加问题, 把所有的逆序对数量加起来即可, 但是这道题是要生成一个数组
• 在递归排序的过程中, 每个数字都有可能会改变位置, 所以要用到 索引数组 来记录下最初的位置, 变相固定下来

public List<Integer> countSmaller(int[] nums) {

    int len = nums.length;
    int[] indexes = new int[len];
    int[] temp = new int[len];
    int[] ans = new int[len];
    List<Integer> res = new ArrayList<>();

    for (int i = 0; i < len; i++) {
        indexes[i] = i;
    }

    mergeSort(nums, 0, len - 1, indexes, temp, ans);

    for (Integer item : ans) {
        res.add(item);
    }

    return res;
}

private void mergeSort(int[] nums, int left, int right, int[] indexes, int[] temp, int[] ans) {
    if (left >= right) {
        return;
    }

    int mid = left + (right - left) / 2;
    mergeSort(nums, left, mid, indexes, temp, ans);
    mergeSort(nums, mid + 1, right, indexes, temp, ans);
    if (nums[indexes[mid]]<=nums[indexes[mid+1]]) {
        return;
    }
    mergeTwoNums(nums, left, mid, right, indexes, temp, ans);
}

private void mergeTwoNums(int[] nums, int left, int mid, int right, int[] indexes, int[] temp, int[] ans) {
    if (right + 1 - left >= 0) {
        System.arraycopy(indexes, left, temp, left, right + 1 - left);
    }

    int l = left;
    int r = mid + 1;

    for (int i = left; i <= right; i++) {
        if (l > mid) {
            indexes[i] = temp[r];
            r++;
        } else if (r > right) {
            indexes[i] = temp[l];
            l++;
            ans[indexes[i]] += right - mid;
        } else if (nums[temp[l]] <= nums[temp[r]]) {
            indexes[i] = temp[l];
            l++;
            ans[indexes[i]] += r - mid - 1;
        } else {
            indexes[i] = temp[r];
            r++;
        }
    }

}

快排(超时)

其实我首先想到的是用快排的思路去做这道题, 但是很遗憾超时了

因为使用快排时并不是将整个数组进行排序, 而仅仅用到了分切的思想, 每次从需要计算的值开始截取数组, 然后进行分切, 最终该数字落在什么位置, 那么就知道比它小的数字有多少个了

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (i == len - 1) {
                res.add(0);
            } else {
                int[] clone = nums.clone();
                res.add(partition(clone, i, len - 1));
            }
        }
        return res;
    }

    private int partition(int[] nums, int left, int right) {
        int pivot = nums[left];
        int lt = left;

        for (int i = left + 1; i <= right; i++) {
            // 注意这里是<=, 解释是如果遇到相同的数, 不能将其视为比自己小
            if (nums[i] < pivot) {
                lt++;
                swap(nums, i, lt);
            }
        }
        swap(nums, lt, left);
        return lt - left;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}