สมมุติว่าในโกดังมีบาร์โค้ดอยู่แถวหนึ่ง บาร์โค้ดที่ i คือบาร์โค้ด[i] เราต้องจัดเรียงบาร์โค้ดใหม่เพื่อไม่ให้บาร์โค้ดที่อยู่ติดกันสองอันเหมือนกัน ดังนั้นหากอินพุตเป็น [1,1,1,2,2,2] เอาต์พุตจะเป็น [2,1,2,1,2,1]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- สร้างแผนที่หนึ่งชื่อ d
- เก็บความถี่ของตัวเลขที่อยู่ในอาร์เรย์บาร์โค้ดลงใน d
- x :=รายการว่าง
- แทรกคู่คีย์-ค่าทั้งหมดลงใน x
- ผม :=0
- res :=ทำรายการความยาวเท่ากับบาร์โค้ด แล้วกรอก [0]
- จัดเรียง x ตามความถี่
- ในขณะที่ฉัน <ความยาวของผลลัพธ์
- ผลลัพธ์[i] :=องค์ประกอบของรายการสุดท้ายของ x
- ลดค่าความถี่ของรายการสุดท้ายของ x
- ถ้าความถี่ขององค์ประกอบสุดท้ายของ x เป็น 0 ให้ลบรายการนั้นออกจาก x
- เพิ่ม i ขึ้น 2
- ผม :=1
- ในขณะที่ฉัน <ความยาวของผลลัพธ์
- ผลลัพธ์[i] :=องค์ประกอบของรายการสุดท้ายของ x
- ลดค่าความถี่ของรายการสุดท้ายของ x
- ถ้าความถี่ขององค์ประกอบสุดท้ายของ x เป็น 0 ให้ลบรายการนั้นออกจาก x
- เพิ่ม i ขึ้น 2
- ผลตอบแทน
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution(object):
def rearrangeBarcodes(self, barcodes):
d = {}
for i in barcodes:
if i not in d:
d[i] = 1
else:
d[i]+=1
x = []
for a,b in d.items():
x.append([a,b])
i = 0
result = [0]*len(barcodes)
x = sorted(x,key=lambda v:v[1])
while i <len(result):
result[i] = x[-1][0]
x[-1][1]-=1
if x[-1][1]==0:
x.pop()
i+=2
i=1
while i <len(result):
result[i] = x[-1][0]
x[-1][1]-=1
if x[-1][1]==0:
x.pop()
i+=2
return result
ob = Solution()
print(ob.rearrangeBarcodes([1,1,1,2,2,2])) อินพุต
[1,1,1,2,2,2]
ผลลัพธ์
[2, 1, 2, 1, 2, 1]
