Giả sử trong kho, có hàng mã vạch. Mã vạch thứ i là barcodes[i]. Ta phải sắp xếp lại sao cho không hai mã vạch liền kề giống nhau. Nếu đầu vào [1,1,1,2,2,2], kết quả [2,1,2,1,2,1].
Để giải quyết, ta làm theo các bước −
- tạo map d
- lưu tần suất số trong barcodes vào d
- x := danh sách rỗng
- thêm tất cả cặp key-value vào x
- i := 0
- result := list độ dài barcodes, điền [0]
- sắp xếp x theo tần suất
- khi i < len(result)
- result[i] := phần tử của entry cuối x
- giảm tần suất entry cuối x
- nếu tần suất entry cuối = 0, xóa entry đó
- tăng i 2
- i := 1
- khi i < len(result)
- result[i] := phần tử của entry cuối x
- giảm tần suất entry cuối x
- nếu tần suất entry cuối = 0, xóa entry đó
- tăng i 2
- trả về result
Xem triển khai sau −
Ví dụ
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]))Đầu vào
[1,1,1,2,2,2]
Kết quả
[2, 1, 2, 1, 2, 1]