สมมติว่าเรามีรายชื่อไพ่ และเราต้องการเรียงลำดับไพ่ในลักษณะที่ไพ่ถูกเปิดเผยในลำดับจากน้อยไปมาก อย่างที่เราทราบ ไพ่ถูกเปิดเผยในลักษณะนี้:1. ไพ่บนสุดจะถูกลบออกและเปิดเผย จากนั้นไพ่ใบต่อไปจะหายไปทางด้านหลัง 2. ขั้นตอนที่ 1 ทำซ้ำจนกว่าจะไม่มีการ์ดอีกต่อไป เราต้องหาลำดับของไพ่ให้เปิดเผยตามลำดับจากน้อยไปมาก
ดังนั้น ถ้าอินพุตเหมือนไพ่ =[1, 2, 3, 4, 5, 6, 7, 8] ผลลัพธ์จะเป็น [1, 5, 2, 7, 3, 6, 4, 8], เนื่องจาก 1 ถูกลบและ 5 ถูกย้ายไปด้านหลังสถานการณ์ปัจจุบัน [2, 7, 3, 6, 4, 8, 5] 2 ถูกลบและ 7 ถูกย้ายไปด้านหลังสถานการณ์ปัจจุบัน [3, 6, 4, 8, 5, 7] 3 ถูกลบและ 6 ถูกย้ายไปด้านหลังสถานการณ์ปัจจุบัน [4, 8, 5, 7, 6] 4 ถูกย้ายออก 8 ถูกย้ายไปด้านหลัง สถานการณ์ปัจจุบัน [5, 7, 6, 8] 5 ถูกลบและ 7 ถูกย้ายไปด้านหลัง สถานการณ์ปัจจุบัน [6, 8, 7] 6 ถูกลบออกและ 8 ถูกย้ายไปด้านหลังสถานการณ์ปัจจุบัน [7, 8] 7 ถูกลบออกและมีการ์ดเพียงใบเดียว [8] จากนั้นลบ [8]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- เรียงลำดับการ์ดรายการ
- idx:=รายการที่มีองค์ประกอบ 0 ถึงความยาวของการ์ด
- order:=รายการใหม่
- q:=คิวและแทรกองค์ประกอบของ idx
- ในขณะที่ q ไม่ใช่ศูนย์ ให้ทำ
- ลบองค์ประกอบจากด้านซ้ายของ q และแทรกลงในลำดับ
- ถ้า q ไม่ใช่ศูนย์ แล้ว
- ans:=ทำรายการขนาดการ์ดและเติม 0
- สำหรับแต่ละองค์ประกอบ i จากคำสั่งและการ์ดจากการ์ด ทำ
- ans[i]:=การ์ด
- คืนสินค้า
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
from collections import deque class Solution: def solve(self, cards): cards.sort() idx=[i for i in range(len(cards))] order=[] q=deque(idx) while q: order.append(q.popleft()) if q: q.append(q.popleft()) ans=[0 for _ in cards] for i,card in zip(order,cards): ans[i]=card return ans ob = Solution() print(ob.solve([1, 2, 3, 4, 5, 6, 7, 8]))
อินพุต
[1, 2, 3, 4, 5, 6, 7, 8]
ผลลัพธ์
[1, 5, 2, 7, 3, 6, 4, 8]
