โจทย์: กำหนดลิสต์บาร์โค้ด จัดเรียงใหม่ให้บาร์โค้ดที่ติดกันไม่เหมือนกัน
ตัวอย่าง
Input: [1,1,1,2,2,2]
Output: [2,1,2,1,2,1]
อัลกอริทึม: Greedy + Even-Odd Placement
- นับความถี่แต่ละบาร์โค้ด
- เรียงตามความถี่มากไปน้อย
- วางบาร์โค้ดที่มากที่สุดในตำแหน่งคู่ (0, 2, 4...)
- วางต่อในตำแหน่งคี่ (1, 3, 5...)
วิธีนี้รับประกันว่าไม่มีตัวติดกัน เพราะตัวที่มากที่สุดถูกกระจายห่างกัน
ตัวอย่างโค้ด Python
class Solution(object):
def rearrangeBarcodes(self, barcodes):
# นับความถี่
freq = {}
for b in barcodes:
freq[b] = freq.get(b, 0) + 1
# เรียงตามความถี่มากไปน้อย
items = sorted(freq.items(), key=lambda x: x[1], reverse=True)
n = len(barcodes)
result = [0] * n
idx = 0
# วางในตำแหน่งคู่ก่อน
for barcode, count in items:
for _ in range(count):
if idx >= n:
idx = 1 # เปลี่ยนไปตำแหน่งคี่
result[idx] = barcode
idx += 2
return result
# ทดสอบ
ob = Solution()
print(ob.rearrangeBarcodes([1,1,1,2,2,2])) # Output: [2, 1, 2, 1, 2, 1]
ตัวอย่าง Input/Output
Input: [1,1,1,2,2,2] Output: [2, 1, 2, 1, 2, 1]
ความซับซ้อน: Time O(n log n), Space O(n)
