การจัดเรียงอาร์เรย์แบบ Relative Sort ใน Python

ให้อาร์เรย์ arr1 และ arr2 arr2 มีค่าไม่ซ้ำ และทุกค่าใน arr2 มีอยู่ใน arr1 จัดเรียง arr1 ให้ลำดับสัมพัทธ์เหมือน arr2 ค่าที่ไม่อยู่ใน arr2 วางท้ายเรียงน้อยไปมาก

ตัวอย่าง: 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]

ขั้นตอนการแก้ปัญหา

1. นับความถี่ทุกค่าใน arr1 เก็บใน map d
2. สร้าง res (ผลลัพธ์) และ temp (ค่าที่ไม่อยู่ใน arr2)
3. วนลูปค่าใน arr2:
   • เพิ่มค่านั้นเข้า res ตามความถี่ใน d
   • ตั้ง d[ค่า] = 0
4. วนลูป d ที่เหลือ (value > 0) เพิ่มเข้า temp
5. เรียง temp แล้วต่อท้าย res

ตัวอย่างโค้ด

class Solution(object):
    def relativeSortArray(self, arr1, arr2):
        d = {}
        for i in arr1:
            d[i] = d.get(i, 0) + 1
        res = []
        temp = []
        for i in arr2:
            res.extend([i] * d[i])
            d[i] = 0
        for k, v in d.items():
            if v:
                temp.extend([k] * v)
        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]

วิธีแก้แบบ Pythonic (ใช้ Counter และ sort key)

from collections import Counter

def relativeSortArray(arr1, arr2):
    order = {v: i for i, v in enumerate(arr2)}
    return sorted(arr1, key=lambda x: (order.get(x, len(arr2)), x))