Pythonで指定されたリストの右側にある小さい要素の数を返すプログラム

numsという番号のリストがあるとすると、新しいリストを作成します。新しいリストの各要素は、元の入力リストのその要素の右側にある小さい要素の数です。

したがって、入力がnums =[4、5、9、7、2]のようである場合、4の右側に1つの小さい要素があるため、出力は[1、1、2、1、0]になります。は5の右側に1つの小さい要素があり、9の右側に2つの小さい要素があり、7の右側に1つの小さい要素があり、2の右側に小さい要素はありません。

これを解決するには、次の手順に従います-

• res：=新しいリスト、inc：=新しいリスト

• numsが空ではない場合は、実行してください

  • num：=numsから最後の要素を削除する

  • 左端のインデックスを挿入して、resの最後にあるincにnumを挿入します

  • incにnumを挿入した後のソート済みリスト

• リストを返す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]