Chương trình trả về số phần tử nhỏ hơn ở bên phải trong Python

Cho danh sách nums, tạo danh sách mới mà mỗi phần tử là số lượng phần tử nhỏ hơn nó ở bên phải trong danh sách gốc.

Ví dụ: nums = [4, 5, 9, 7, 2] → kết quả [1, 1, 2, 1, 0].

Giải thuật (Duyệt ngược + Danh sách đã sắp xếp + Bisect)

1. Khởi tạo res = [], inc = [] (danh sách đã sắp xếp các phần tử đã duyệt).
2. Duyệt nums từ cuối về đầu (pop()):
   • Lấy num = nums.pop().
   • Dùng bisect_left(inc, num) tìm vị trí chèn → chính là số phần tử nhỏ hơn num trong inc.
   • Thêm vị trí này vào res.
   • Chèn vào inc giữ thứ tự sắp xếp (bisect.insort).
3. Đảo ngược res và trả về.

Ví dụ minh họa

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))  # Output: [1, 1, 2, 1, 0]

Đầu vào

[4, 5, 9, 7, 2]

Đầu ra

[1, 1, 2, 1, 0]