Title

給定一個(gè)整數(shù)數(shù)組 nums，按要求返回一個(gè)新數(shù)組 counts。數(shù)組 counts 有該性質(zhì)： counts[i] 的值是 nums[i] 右側(cè)小于 nums[i] 的元素的數(shù)量。

示例:

輸入: [5,2,6,1]
輸出: [2,1,1,0]

解釋:
5 的右側(cè)有 2 個(gè)更小的元素 (2 和 1).
2 的右側(cè)僅有 1 個(gè)更小的元素 (1).
6 的右側(cè)有 1 個(gè)更小的元素 (1).
1 的右側(cè)有 0 個(gè)更小的元素.

二分插入排序

把輸入數(shù)組反過來(lái)插入一個(gè)有序數(shù)組（降序）中，插入的位置就是在原數(shù)組中位于它右側(cè)的元素的個(gè)數(shù)。

初始狀態(tài)：

原數(shù)組為：[5,2,6,1] 排序數(shù)組：[] 結(jié)果數(shù)組：[]

第一輪：

原數(shù)組為：[5,2,6] 排序數(shù)組：[1] 插入的下標(biāo)為 0，記入結(jié)果數(shù)組：[0]

第二輪：

原數(shù)組為：[5,2] 排序數(shù)組：[1,6] 插入的下標(biāo)為 1，記入結(jié)果數(shù)組：[0,1]

第三輪：

原數(shù)組為：[5] 排序數(shù)組：[1,2,6] 插入的下標(biāo)為 1，記入結(jié)果數(shù)組：[0,1,1]

第四輪：

原數(shù)組為：[] 排序數(shù)組：[1,2,5,6] 插入的下標(biāo)為 2，記入結(jié)果數(shù)組：[0,1,1,2]

Code

class Solution:def countSmaller(self, nums: List[int]) -> List[int]:res, sortns = [], []for i in reversed(nums):idx = bisect.bisect_left(sortns, i)res.append(idx)sortns.insert(idx,i)return res[::-1]

總結(jié)

以上是生活随笔為你收集整理的315. Count of Smaller Numbers After Self 计算右侧小于当前元素的个数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。