สมมติว่าเรามีอาร์เรย์สองอาร์เรย์ arr1 และ arr2 องค์ประกอบของ arr2 มีลักษณะเฉพาะ และองค์ประกอบทั้งหมดใน arr2 ก็มีอยู่ใน arr1 ด้วย เราต้องจัดเรียงองค์ประกอบของ arr1 ในลักษณะที่การเรียงลำดับแบบสัมพัทธ์ของรายการใน arr1 เหมือนกับใน arr2 หากมีองค์ประกอบบางอย่างที่ไม่มีอยู่ใน arr2 ควรวางไว้ที่ส่วนท้ายของ arr1 โดยเรียงลำดับจากน้อยไปมาก ดังนั้นถ้า arr1 เป็นเหมือน [2,3,1,3,2,4,6,7,9,2,19] และ arr2 เป็นเหมือน [2,1,4,3,9,6] ก็จะได้ผลลัพธ์ จะเป็น [2,2,2,1,4,3,3,9,6,7,19]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- สร้างแผนที่ชื่อ D และเก็บความถี่ขององค์ประกอบที่อยู่ใน arr1
- กำหนด res และ temp สองอาร์เรย์
- สำหรับแต่ละองค์ประกอบ i ใน arr2 −
- สำหรับ j ในช่วง 0 ถึง D[i] – 1
- เติม i ลงใน res
- D[i] :=0
- สำหรับ j ในช่วง 0 ถึง D[i] – 1
- สำหรับ (คีย์, ค่า) คู่ใน D
- ถ้าค่าไม่ใช่ 0 แล้ว
- สำหรับ i :=0 ถึงค่า – 1
- เพิ่มคีย์ลงใน temp
- สำหรับ i :=0 ถึงค่า – 1
- ถ้าค่าไม่ใช่ 0 แล้ว
- จัดเรียง temp array เพิ่ม temp ที่ส่วนท้ายของ res และคืนค่า res
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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])) อินพุต
[2,3,1,3,2,4,6,7,9,2,19] [2,1,4,3,9,6]
ผลลัพธ์
[2, 2, 2, 1, 4, 4, 3, 9, 6, 7, 19]
