Chương trình sắp xếp mảng theo tần suất tăng dần trong Python

Giả sử ta có mảng với các phần tử có thể xuất hiện nhiều lần. Sắp xếp mảng sao cho các phần tử được sắp theo tần suất tăng dần. Phần tử xuất hiện ít lần đứng trước.

Ví dụ: nums = [1,5,3,1,3,1,2,5], kết quả [2, 5, 5, 3, 3, 1, 1, 1].

Giải thuật

1. mp := {} (map tần suất → danh sách phần tử)
2. Với mỗi i duy nhất trong nums:
   • x := nums.count(i)
   • Nếu x trong mp: thêm i vào mp[x]
   • Ngược lại: mp[x] = [i]
3. ans := []
4. Với mỗi i trong sorted(mp) (theo key tăng dần):
   • Với mỗi j trong sorted(mp[i], reverse=True):
     • Thêm j lặp i lần vào ans
5. Trả về ans

Ví dụ (Python)

def solve(nums):
    mp = {}
    for i in set(nums):
        x = nums.count(i)
        try:
            mp[x].append(i)
        except:
            mp[x] = [i]
    ans = []
    for i in sorted(mp):
        for j in sorted(mp[i], reverse=True):
            ans.extend([j] * i)
    return ans

nums = [1, 5, 3, 1, 3, 1, 2, 5]
print(solve(nums))

Input

[1,5,3,1,3,1,2,5]

Output

[2, 5, 5, 3, 3, 1, 1, 1]