Python程序：返回给定列表右侧较小元素的数量

假设我们有一个名为nums的数字列表，我们将创建一个新的列表，其中新列表中的每个元素都是原始输入列表中该元素右侧较小元素的数量。

因此，如果输入类似于nums = [4, 5, 9, 7, 2]，则输出将为[1, 1, 2, 1, 0]，因为4的右侧有1个较小元素，5的右侧有1个较小元素，9的右侧有2个较小元素，7的右侧有1个较小元素，2的右侧没有较小元素。

为了解决这个问题，我们将遵循以下步骤：

  • res := 新列表，inc := 新列表

  • 当nums不为空时，执行以下操作：

    • num := 从nums中删除最后一个元素

    • 将插入num到inc中的最左索引插入到res的末尾

    • 插入num到inc后排序的列表

  • 返回列表res[从索引0到结尾]

让我们看看下面的实现，以便更好地理解：

示例

在线演示

import bisect
class Solution:
   def solve(self, nums):
      res, inc = [], []
      while nums:
         num = nums.pop()
         res.append(bisect.bisect_left(inc, num))
         bisect.insort(inc, num)
      return res[::-1]
ob = Solution()
nums = [4, 5, 9, 7, 2]
print(ob.solve(nums))

输入

[4, 5, 9, 7, 2]

输出

[1, 1, 2, 1, 0]

更新于：2020年10月10日

309 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告