Leetcode: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 归并排序+索引数组

代码

代码1

class Solution {
    public List countSmaller(int[] nums) {
        ArrayList result = new ArrayList<>();
        for(int i = 0; i < nums.length; i++){
            int count = 0;
            for(int j = i + 1; j < nums.length; j++){
                if (nums[i] > nums[j]){
                    count += 1;
                }
            }
            result.add(count);
        }
        return result;
    }
}

代码2

class Solution {
    private int[] indexs;
    private int[] counters;
    private int[] temp;
    
    public List countSmaller(int[] nums) {
        ArrayList result = new ArrayList<>();
        indexs = new int[nums.length];
        counters = new int[nums.length];
        temp = new int[nums.length];
        for(int i = 0; i < nums.length; i++){
            indexs[i] = i;
            counters[i] = 0;
        }
        mergeSort(nums, 0, nums.length - 1);
        for(int i = 0; i < counters.length; i++){
            result.add(counters[i]);
        }
        return result;
    }
    
    
    private void mergeSort(int[] nums, int left, int right){
        if (left < right){
            int mid = (left + right) / 2;
            mergeSort(nums, left, mid);
            mergeSort(nums, mid + 1, right);
            mergeHelper(nums, left, mid, right);
        }
    }
    
    private void mergeHelper(int[] nums, int left, int mid , int right){
        int tempIndex = left;
        int leftIndex = left;
        int rightIndex = mid + 1;
        while (leftIndex <= mid && rightIndex <= right){
            if (nums[indexs[leftIndex]] <= nums[indexs[rightIndex]]){
                temp[tempIndex] = indexs[leftIndex];
                counters[indexs[leftIndex]] += rightIndex - mid - 1;
                leftIndex++;
            }else{
                temp[tempIndex] = indexs[rightIndex];
                rightIndex++;
            }
            tempIndex++;
        }
        while(leftIndex <= mid){
            temp[tempIndex] = indexs[leftIndex];
            counters[indexs[leftIndex]] += rightIndex - mid - 1;
            leftIndex++;
            tempIndex++;
        }
        while(rightIndex <= right){
            temp[tempIndex] = indexs[rightIndex];
            rightIndex++;
            tempIndex++;
        }
        for(int i = left; i <= right; i++){
            indexs[i] = temp[i];
        }
    }
}