Sắp Xếp Mảng Tương Đối (Relative Sort Array) Trong Python

Cho 2 mảng arr1, arr2. Phần tử arr2 đều duy nhất và xuất hiện trong arr1. Sắp xếp arr1 sao cho:

1. Phần tử trong arr2 xuất hiện theo đúng thứ tự của arr2
2. Phần tử không trong arr2 đặt cuối, sắp xếp tăng dần

Ví dụ: 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]

Thuật toán

1. Đếm tần suất phần tử trong arr1 → Counter
2. Duyệt arr2: thêm phần tử vào kết quả theo tần suất, đặt count = 0
3. Thu thập phần tử còn lại (count > 0), sắp xếp, nối vào kết quả

Ví dụ (Python)

from collections import Counter

class Solution(object):
    def relativeSortArray(self, arr1, arr2):
        freq = Counter(arr1)
        res = []
        
        # Phần tử trong arr2 - giữ thứ tự
        for x in arr2:
            res.extend([x] * freq[x])
            freq[x] = 0
        
        # Phần tử còn lại - sắp xếp tăng
        remaining = []
        for x, count in freq.items():
            if count > 0:
                remaining.extend([x] * count)
        remaining.sort()
        res.extend(remaining)
        
        return res

ob1 = Solution()
print(ob1.relativeSortArray([2,3,1,3,2,4,6,7,9,2,19], [2,1,4,3,9,6]))
# [2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19]

Độ phức tạp

• Thời gian: O(n log n) (do sort phần tử còn lại)
• Không gian: O(n)

Đầu vào / Đầu ra

Input:  arr1 = [2,3,1,3,2,4,6,7,9,2,19]
        arr2 = [2,1,4,3,9,6]
Output: [2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19]