Giả sử chúng ta có một danh sách các số được gọi là num, chúng ta sẽ tạo một danh sách mới trong đó mỗi phần tử trong danh sách mới là số phần tử nhỏ hơn ở phía bên tay phải của phần tử đó trong danh sách đầu vào nguyên thủy.
Vì vậy, nếu đầu vào giống như nums =[4, 5, 9, 7, 2], thì đầu ra sẽ là [1, 1, 2, 1, 0], vì có 1 phần tử nhỏ hơn ở bên phải của 4, ở đó là 1 phần tử nhỏ hơn ở bên phải của 5, có 2 phần tử nhỏ hơn ở bên phải của 9, có 1 phần tử nhỏ hơn ở bên phải của 7, không có phần tử nào nhỏ hơn ở bên phải của 2.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
res:=a new list, inc:=a new list
-
trong khi nums không trống, hãy thực hiện
-
num:=xóa phần tử cuối cùng khỏi nums
-
chèn chỉ mục ngoài cùng bên trái để chèn num trong inc ở cuối res
-
danh sách được sắp xếp sau khi chèn num trong inc
-
-
trả về res một danh sách [từ chỉ mục 0 đến cuối]
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn−
Ví dụ
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))
Đầu vào
[4, 5, 9, 7, 2]
Đầu ra
[1, 1, 2, 1, 0]