สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums เราจะสร้างรายการใหม่ โดยที่แต่ละองค์ประกอบในรายการใหม่คือจำนวนขององค์ประกอบที่เล็กกว่าทางด้านขวามือขององค์ประกอบนั้นในรายการอินพุตดั้งเดิม
ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[4, 5, 9, 7, 2] ผลลัพธ์จะเป็น [1, 1, 2, 1, 0] เนื่องจากมี 1 องค์ประกอบเล็กกว่าทางด้านขวาของ 4 คือองค์ประกอบที่เล็กกว่า 1 รายการทางด้านขวาของ 5 มีองค์ประกอบขนาดเล็กกว่า 2 รายการทางด้านขวาของ 9 องค์ประกอบที่เล็กกว่า 1 รายการทางด้านขวาของ 7 ไม่มีองค์ประกอบที่เล็กกว่าทางด้านขวาของ 2
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
res :=รายการใหม่ inc :=รายการใหม่
-
ในขณะที่ nums ไม่ว่างเปล่าให้ทำ
-
num :=ลบองค์ประกอบสุดท้ายออกจาก nums
-
แทรกซ้ายดัชนีมากที่สุดเพื่อแทรก num inc ที่ส่วนท้ายของความละเอียด
-
เรียงลำดับรายการหลังจากใส่ 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]
