สมมติว่าเรามีรายการตัวเลข nums เราจะสร้างรายการใหม่ที่แต่ละองค์ประกอบคือจำนวนองค์ประกอบที่น้อยกว่าองค์ประกอบนั้นอยู่ทางด้านขวาในรายการเดิม
ตัวอย่างเช่น หาก nums = [4, 5, 9, 7, 2] ผลลัพธ์จะเป็น [1, 1, 2, 1, 0] เนื่องจาก:
- ทางขวาของ 4 มีค่าน้อยกว่า 1 ตัว (คือ 2)
- ทางขวาของ 5 มีค่าน้อยกว่า 1 ตัว (คือ 2)
- ทางขวาของ 9 มีค่าน้อยกว่า 2 ตัว (คือ 7, 2)
- ทางขวาของ 7 มีค่าน้อยกว่า 1 ตัว (คือ 2)
- ทางขวาของ 2 ไม่มีค่าน้อยกว่า
ขั้นตอนการแก้ปัญหา (Binary Indexed Tree / Bisect)
- สร้าง
res = [](เก็บผลลัพธ์),inc = [](รายการที่เรียงแล้ว) - วนลูป while
numsไม่ว่าง:num = nums.pop()(นำตัวสุดท้ายออก)- หา index ที่จะ insert
numในincด้วยbisect_leftและเพิ่มเข้าres - Insert
numเข้าincแบบเรียงลำดับด้วยbisect.insort
- คืนค่า
res[::-1](กลับลำดับเพราะประมวลผลจากท้ายไปหน้า)
ตัวอย่างโค้ด Python
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]
อินพุต
[4, 5, 9, 7, 2]
เอาต์พุต
[1, 1, 2, 1, 0]
