[LeetCode] 315. Count of Smaller Numbers After Self (Hard)

315. Count of Smaller Numbers After Self

class Solution {

public:

    vector<int> countSmaller(vector<int>& nums) {

        int n = nums.size();

        vector<int> v(n);

        for (int i = n - 1; i >= 0; --i) {

            int val = nums[i];

            int L = i + 1, R = n - 1;

            while (L <= R) {

                int M = L + (R - L) / 2;

                if (nums[M] >= val) {

                    L = M + 1;

                } else {

                    R = M - 1;

                }

            }

            for (int j = i; j < R; ++j) {

                nums[j] = nums[j + 1];

            }

            nums[R] = val;

            v[i] = n - R - 1;

        }

        return v;

    }

};

// 1320 ms

算法思想: 从右端折半插入. 对于每个数字来说, 数组长度 - 插入后的位置 - 1就是该数字的count.

时间复杂度: O(n^2).

空间复杂度: O(1).

还有更快的方法. 以后更新.

巴特西

[LeetCode] 315. Count of Smaller Numbers After Self (Hard)

最新文章

热门文章