Hard

题目描述

给你一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质：counts[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：

输入：nums = [-1]
输出：[0]

示例 3：

输入：nums = [-1,-1]
输出：[0,0]

提示：

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

解题思路

这道题要求计算每个元素右侧小于它的元素个数。可以从以下几个角度考虑：

暴力解法：对每个元素遍历其右侧所有元素，时间复杂度 O(n²)，会超时。

优化思路：

  1. 归并排序思路：从右往左处理元素，维护一个已排序的数组，对于当前元素，在已排序数组中二分查找第一个大于等于它的位置。
  2. 离散化+树状数组：将数值映射到较小范围，使用树状数组统计频次。
  3. 平衡二叉搜索树：维护右侧已访问元素的有序集合。

推荐解法 - 归并排序 + 二分查找：

  • 从右往左遍历数组
  • 维护一个已排序的数组 sorted_nums 存储右侧已遍历的元素
  • 对当前元素 nums[i]，在 sorted_nums 中二分查找第一个大于等于它的位置
  • 该位置就是小于 nums[i] 的元素个数
  • 将 nums[i] 插入 sorted_nums 中保持有序

这种方法利用了二分查找的效率，每次查找和插入的时间复杂度为 O(log n)，总体复杂度为 O(n log n)。

代码实现

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n);
        vector<int> sorted_nums;
        
        for (int i = n - 1; i >= 0; i--) {
            auto pos = lower_bound(sorted_nums.begin(), sorted_nums.end(), nums[i]);
            result[i] = pos - sorted_nums.begin();
            sorted_nums.insert(pos, nums[i]);
        }
        
        return result;
    }
};

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        from bisect import bisect_left, insort
        
        result = []
        sorted_nums = []
        
        for i in range(len(nums) - 1, -1, -1):
            pos = bisect_left(sorted_nums, nums[i])
            result.append(pos)
            insort(sorted_nums, nums[i])
        
        return result[::-1]

public class Solution {
    public IList<int> CountSmaller(int[] nums) {
        int n = nums.Length;
        int[] result = new int[n];
        List<int> sortedNums = new List<int>();
        
        for (int i = n - 1; i >= 0; i--) {
            int pos = BinarySearch(sortedNums, nums[i]);
            result[i] = pos;
            sortedNums.Insert(pos, nums[i]);
        }
        
        return result;
    }
    
    private int BinarySearch(List<int> list, int target) {
        int left = 0, right = list.Count;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (list[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

var countSmaller = function(nums) {
    const result = new Array(nums.length);
    const sortedNums = [];
    
    for (let i = nums.length - 1; i >= 0; i--) {
        const pos = binarySearch(sortedNums, nums[i]);
        result[i] = pos;
        sortedNums.splice(pos, 0, nums[i]);
    }
    
    return result;
    
    function binarySearch(arr, target) {
        let left = 0, right = arr.length;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

指标复杂度
时间复杂度O(n²)
空间复杂度O(n)

说明：

  • 时间复杂度：虽然二分查找是 O(log n)，但每次插入操作在最坏情况下需要移动 O(n) 个元素，总体为 O(n²)
  • 空间复杂度：需要额外的数组存储已排序元素，空间复杂度为 O(n)
  • 对于更优的 O(n log n) 解法，可以考虑使用树状数组或线段树，但实现复杂度较高

相关题目