Giả sử chúng ta có hai mảng arr1 và arr2, các phần tử của arr2 là duy nhất và tất cả các phần tử trong arr2 cũng có trong arr1. Chúng ta phải sắp xếp các phần tử của arr1 sao cho thứ tự tương đối của các mục trong arr1 giống như trong arr2. Nếu có một số phần tử không có trong arr2, chúng nên được đặt ở cuối arr1 theo thứ tự tăng dần. Vì vậy, nếu arr1 giống như [2,3,1,3,2,4,6,7,9,2,19] và arr2 giống như [2,1,4,3,9,6], thì kết quả sẽ là [2,2,2,1,4,3,3,9,6,7,19]
Để 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 và lưu trữ tần suất của các phần tử có trong arr1
- xác định hai mảng res và temp
- cho mỗi phần tử i trong arr2 -
- cho j trong phạm vi từ 0 đến D [i] - 1
- nối tôi vào res
- D [i]:=0
Cặp - cho j trong phạm vi từ 0 đến D [i] - 1
- for (key, value) trong D
- nếu giá trị không phải là 0, thì
- for i:=0 to value - 1
- thêm khóa vào tạm thời
- for i:=0 to value - 1
- nếu giá trị không phải là 0, thì
- sắp xếp mảng tạm thời, thêm nhiệt độ vào cuối res và trả về res
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
class Solution(object):
def relativeSortArray(self, arr1, arr2):
d = {}
for i in arr1:
if i not in d:
d[i]= 1
else:
d[i]+=1
res = []
temp = []
for i in arr2:
for j in range(d[i]):
res.append(i)
d[i] =0
for k,v in d.items():
if v:
for i in range(v):
temp.append(k)
temp.sort()
res.extend(temp)
return res
ob1 = Solution()
print(ob1.relativeSortArray([2,3,1,4,2,4,6,7,9,2,19] ,[2,1,4,3,9,6])) Đầu vào
[2,3,1,3,2,4,6,7,9,2,19] [2,1,4,3,9,6]
Đầu ra
[2, 2, 2, 1, 4, 4, 3, 9, 6, 7, 19]