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

困难二分查找从右往左二分插入有序数组力扣原题 ↗

题目描述

输入一个整数数组 nums。

返回一个与它等长的数组 counts，其中 counts[i] 等于下标在 i 之后、并且严格小于 nums[i] 的元素个数。

示例 1

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

解释：5 右边比它小的有 2 和 1；2 右边有 1；6 右边有 1；1 右边没有元素。

示例 2

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

解释：只有一个元素，右边为空。

示例 3

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

解释：相等的数不算更小。

数据范围

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

解题思路：从右往左二分插入有序数组

从右往左扫描，把扫过的数放进一个始终有序的列表 seen。处理 nums[i] 时，seen 恰好是它右边的所有数；在 seen 上用 bisect_left 二分出 nums[i] 的插入位置 pos，pos 左边的数都严格小于 nums[i]，所以答案就是 pos。再把 nums[i] 插到 pos，保持有序。

为什么正确

处理到下标 i 时，seen 是 nums[i+1:] 的升序排列。

复杂度分析

二分 O(log n)，列表插入 O(n)，总时间最坏 O(n^2)（实际很快；要严格 O(n log n) 可换树状数组或归并排序）；空间 O(n)。

易错点

必须用 bisect_left（第一个 >= x 的位置）。用 bisect_right 会把右边等于 nums[i] 的数也算成“更小”。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        seen = []
        res = [0] * len(nums)
        for i in range(len(nums) - 1, -1, -1):
            pos = bisect_left(seen, nums[i])
            res[i] = pos
            seen.insert(pos, nums[i])
        return res

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> seen = new ArrayList<>();
        Integer[] res = new Integer[nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            int lo = 0, hi = seen.size();
            while (lo < hi) {
                int mid = (lo + hi) / 2;
                if (seen.get(mid) < nums[i]) lo = mid + 1;
                else hi = mid;
            }
            int pos = lo;
            res[i] = pos;
            seen.add(pos, nums[i]);
        }
        return Arrays.asList(res);
    }
}

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

func countSmaller(nums []int) []int {
	seen := []int{}
	res := make([]int, len(nums))
	for i := len(nums) - 1; i >= 0; i-- {
		pos := sort.SearchInts(seen, nums[i])
		res[i] = pos
		seen = append(seen, 0)
		copy(seen[pos+1:], seen[pos:])
		seen[pos] = nums[i]
	}
	return res
}

var countSmaller = function(nums) {
    const seen = [];
    const res = new Array(nums.length).fill(0);
    for (let i = nums.length - 1; i >= 0; i--) {
        let lo = 0, hi = seen.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (seen[mid] < nums[i]) lo = mid + 1;
            else hi = mid;
        }
        const pos = lo;
        res[i] = pos;
        seen.splice(pos, 0, nums[i]);
    }
    return res;
};

function countSmaller(nums: number[]): number[] {
    const seen: number[] = [];
    const res = new Array(nums.length).fill(0);
    for (let i = nums.length - 1; i >= 0; i--) {
        let lo = 0, hi = seen.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (seen[mid] < nums[i]) lo = mid + 1;
            else hi = mid;
        }
        const pos = lo;
        res[i] = pos;
        seen.splice(pos, 0, nums[i]);
    }
    return res;
}

载入编辑器，自己跑一遍 →

其他解法

主解法直观，但列表插入是 O(n)，最坏 O(n²)；归并排序在合并时顺带统计“从右边越过来的更小元素”；树状数组把问题变成值域上的前缀计数。后两者都是严格的 O(n log)。

解法 2：归并排序统计时间 O(n log n)，空间 O(n)

对下标数组按值做归并排序。合并左右两个有序段时，若左段元素 nums[l[i]] <= 右段当前元素，就放入左段元素，并把右段已弹出的个数 j 累加到 res[l[i]]：这 j 个元素都在它右边，且严格更小。左段剩余元素同样累加 j。

最坏情况也是 O(n log n)，且不依赖值域，是“逆序对”类问题的通用模板。要排序下标而不是值，还要注意相等时先放左边，细节较多。

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [0] * n

        def sort(idx):
            if len(idx) <= 1:
                return idx
            mid = len(idx) // 2
            left, right = sort(idx[:mid]), sort(idx[mid:])
            merged = []
            j = 0
            for i in left:
                while j < len(right) and nums[right[j]] < nums[i]:
                    merged.append(right[j])
                    j += 1
                res[i] += j
                merged.append(i)
            merged.extend(right[j:])
            return merged

        sort(list(range(n)))
        return res

class Solution {
    private int[] nums, idx, tmp, res;

    private void sort(int lo, int hi) {
        if (hi - lo <= 1) return;
        int mid = (lo + hi) >>> 1;
        sort(lo, mid);
        sort(mid, hi);
        int j = mid, k = lo;
        for (int i = lo; i < mid; i++) {
            while (j < hi && nums[idx[j]] < nums[idx[i]]) tmp[k++] = idx[j++];
            res[idx[i]] += j - mid;
            tmp[k++] = idx[i];
        }
        while (j < hi) tmp[k++] = idx[j++];
        System.arraycopy(tmp, lo, idx, lo, hi - lo);
    }

    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        this.nums = nums;
        idx = new int[n];
        tmp = new int[n];
        res = new int[n];
        for (int i = 0; i < n; i++) idx[i] = i;
        sort(0, n);
        List<Integer> out = new ArrayList<>();
        for (int x : res) out.add(x);
        return out;
    }
}

class Solution {
    vector<int> idx, tmp, res;

    void sort(const vector<int>& nums, int lo, int hi) {
        if (hi - lo <= 1) return;
        int mid = (lo + hi) / 2;
        sort(nums, lo, mid);
        sort(nums, mid, hi);
        int j = mid, k = lo;
        for (int i = lo; i < mid; i++) {
            while (j < hi && nums[idx[j]] < nums[idx[i]]) tmp[k++] = idx[j++];
            res[idx[i]] += j - mid;
            tmp[k++] = idx[i];
        }
        while (j < hi) tmp[k++] = idx[j++];
        for (int i = lo; i < hi; i++) idx[i] = tmp[i];
    }

public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        idx.resize(n);
        tmp.resize(n);
        res.assign(n, 0);
        for (int i = 0; i < n; i++) idx[i] = i;
        sort(nums, 0, n);
        return res;
    }
};

func countSmaller(nums []int) []int {
	n := len(nums)
	idx := make([]int, n)
	tmp := make([]int, n)
	res := make([]int, n)
	for i := range idx {
		idx[i] = i
	}
	var sort func(lo, hi int)
	sort = func(lo, hi int) {
		if hi-lo <= 1 {
			return
		}
		mid := (lo + hi) / 2
		sort(lo, mid)
		sort(mid, hi)
		j, k := mid, lo
		for i := lo; i < mid; i++ {
			for j < hi && nums[idx[j]] < nums[idx[i]] {
				tmp[k] = idx[j]
				k++
				j++
			}
			res[idx[i]] += j - mid
			tmp[k] = idx[i]
			k++
		}
		for ; j < hi; j++ {
			tmp[k] = idx[j]
			k++
		}
		copy(idx[lo:hi], tmp[lo:hi])
	}
	sort(0, n)
	return res
}

var countSmaller = function(nums) {
    const n = nums.length;
    const idx = Array.from({ length: n }, (_, i) => i);
    const tmp = new Array(n);
    const res = new Array(n).fill(0);
    const sort = (lo, hi) => {
        if (hi - lo <= 1) return;
        const mid = (lo + hi) >> 1;
        sort(lo, mid);
        sort(mid, hi);
        let j = mid, k = lo;
        for (let i = lo; i < mid; i++) {
            while (j < hi && nums[idx[j]] < nums[idx[i]]) tmp[k++] = idx[j++];
            res[idx[i]] += j - mid;
            tmp[k++] = idx[i];
        }
        while (j < hi) tmp[k++] = idx[j++];
        for (let i = lo; i < hi; i++) idx[i] = tmp[i];
    };
    sort(0, n);
    return res;
};

function countSmaller(nums: number[]): number[] {
    const n = nums.length;
    const idx: number[] = Array.from({ length: n }, (_, i) => i);
    const tmp: number[] = new Array(n);
    const res: number[] = new Array(n).fill(0);
    const sort = (lo: number, hi: number): void => {
        if (hi - lo <= 1) return;
        const mid = (lo + hi) >> 1;
        sort(lo, mid);
        sort(mid, hi);
        let j = mid, k = lo;
        for (let i = lo; i < mid; i++) {
            while (j < hi && nums[idx[j]] < nums[idx[i]]) tmp[k++] = idx[j++];
            res[idx[i]] += j - mid;
            tmp[k++] = idx[i];
        }
        while (j < hi) tmp[k++] = idx[j++];
        for (let i = lo; i < hi; i++) idx[i] = tmp[i];
    };
    sort(0, n);
    return res;
}

解法 3：树状数组（值域计数）时间 O(n log V)，空间 O(V)

从右往左遍历，用树状数组维护“右侧已出现的每个值的个数”。先把值域 [-10^4, 10^4] 平移到 [1, 20001]；处理 nums[i] 时，前缀和 query(v-1) 就是右侧严格更小的个数，然后 update(v, 1)。

代码短，单次操作 O(log V)。当值域很大时要先离散化（排序去重后映射到排名）。

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        OFFSET, SIZE = 10001, 20002
        tree = [0] * (SIZE + 1)

        def update(i):
            while i <= SIZE:
                tree[i] += 1
                i += i & -i

        def query(i):
            s = 0
            while i > 0:
                s += tree[i]
                i -= i & -i
            return s

        res = [0] * len(nums)
        for i in range(len(nums) - 1, -1, -1):
            v = nums[i] + OFFSET
            res[i] = query(v - 1)
            update(v)
        return res

class Solution {
    private static final int OFFSET = 10001, SIZE = 20002;
    private final int[] tree = new int[SIZE + 1];

    private void update(int i) {
        for (; i <= SIZE; i += i & -i) tree[i]++;
    }

    private int query(int i) {
        int s = 0;
        for (; i > 0; i -= i & -i) s += tree[i];
        return s;
    }

    public List<Integer> countSmaller(int[] nums) {
        Integer[] res = new Integer[nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            int v = nums[i] + OFFSET;
            res[i] = query(v - 1);
            update(v);
        }
        return Arrays.asList(res);
    }
}

class Solution {
    static const int OFFSET = 10001, SIZE = 20002;
    vector<int> tree;

    void update(int i) {
        for (; i <= SIZE; i += i & -i) tree[i]++;
    }

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

public:
    vector<int> countSmaller(vector<int>& nums) {
        tree.assign(SIZE + 1, 0);
        int n = nums.size();
        vector<int> res(n);
        for (int i = n - 1; i >= 0; i--) {
            int v = nums[i] + OFFSET;
            res[i] = query(v - 1);
            update(v);
        }
        return res;
    }
};

func countSmaller(nums []int) []int {
	const offset, size = 10001, 20002
	tree := make([]int, size+1)
	update := func(i int) {
		for ; i <= size; i += i & -i {
			tree[i]++
		}
	}
	query := func(i int) int {
		s := 0
		for ; i > 0; i -= i & -i {
			s += tree[i]
		}
		return s
	}
	res := make([]int, len(nums))
	for i := len(nums) - 1; i >= 0; i-- {
		v := nums[i] + offset
		res[i] = query(v - 1)
		update(v)
	}
	return res
}

var countSmaller = function(nums) {
    const OFFSET = 10001, SIZE = 20002;
    const tree = new Int32Array(SIZE + 1);
    const update = (i) => {
        for (; i <= SIZE; i += i & -i) tree[i]++;
    };
    const query = (i) => {
        let s = 0;
        for (; i > 0; i -= i & -i) s += tree[i];
        return s;
    };
    const res = new Array(nums.length);
    for (let i = nums.length - 1; i >= 0; i--) {
        const v = nums[i] + OFFSET;
        res[i] = query(v - 1);
        update(v);
    }
    return res;
};

function countSmaller(nums: number[]): number[] {
    const OFFSET = 10001, SIZE = 20002;
    const tree = new Int32Array(SIZE + 1);
    const update = (i: number): void => {
        for (; i <= SIZE; i += i & -i) tree[i]++;
    };
    const query = (i: number): number => {
        let s = 0;
        for (; i > 0; i -= i & -i) s += tree[i];
        return s;
    };
    const res: number[] = new Array(nums.length);
    for (let i = nums.length - 1; i >= 0; i--) {
        const v = nums[i] + OFFSET;
        res[i] = query(v - 1);
        update(v);
    }
    return res;
}

二分查找专题的其他题目

查看二分查找全部题目 →