Giả sử trong một nhà kho, có một hàng mã vạch. Mã vạch thứ i là mã vạch [i]. Chúng ta phải sắp xếp lại các mã vạch để không có hai mã vạch liền kề nào giống nhau. Vì vậy, nếu đầu vào là [1,1,1,2,2,2] thì đầu ra là [2,1,2,1,2,1].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- tạo một bản đồ có tên là d
- lưu trữ tần suất của các số có trong mảng mã vạch vào d
- x:=danh sách trống
- chèn tất cả các cặp khóa-giá trị vào x
- i:=0
- res:=tạo một danh sách có độ dài bằng với mã vạch và điền vào [0]
- sắp xếp x dựa trên tần suất
- while i <độ dài của kết quả
- result [i]:=phần tử của mục nhập cuối cùng của x
- giảm giá trị tần suất của mục nhập cuối cùng của x
- nếu tần suất của phần tử cuối cùng của x là 0, thì hãy xóa mục nhập đó khỏi x
- tăng tôi lên 2
- i:=1
- while i <độ dài của kết quả
- result [i]:=phần tử của mục nhập cuối cùng của x
- giảm giá trị tần suất của mục nhập cuối cùng của x
- nếu tần suất của phần tử cuối cùng của x là 0, thì hãy xóa mục nhập đó khỏi x
- tăng tôi lên 2
- trả về kết quả
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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]
Đầu ra
[2, 1, 2, 1, 2, 1]