เรียง Array ให้ Element ที่มีความถี่ (Frequency) น้อยกว่าอยู่หน้า ถ้าความถี่เท่ากัน เรียงตามค่าตัวเลขจากมากไปน้อย (Descending)
ตัวอย่าง
- Input:
nums = [1, 5, 3, 1, 3, 1, 2, 5] - Frequency: 1→3, 5→2, 3→2, 2→1
- Output:
[2, 5, 5, 3, 3, 1, 1, 1]
Sorted by Frequency Asc, then Value Desc: Freq 1: [2] → 2 Freq 2: [5, 3] → 5, 5, 3, 3 (5 > 3) Freq 3: [1] → 1, 1, 1 Result: [2, 5, 5, 3, 3, 1, 1, 1]
โค้ด Python
from collections import Counter
def frequency_sort(nums):
"""
เรียง Array ตามความถี่น้อยไปมาก ค่ามากไปน้อยเมื่อ Frequency เท่ากัน
Args:
nums: List[int]
Returns:
List[int] - Sorted Array
"""
# นับความถี่
freq = Counter(nums)
# เรียง: Primary = Frequency (Asc), Secondary = Value (Desc)
# Key: (freq[x], -x) เพราะ Python Sort เป็น Ascending
return sorted(nums, key=lambda x: (freq[x], -x))
# ทดสอบ
if __name__ == "__main__":
# Test Case 1
nums = [1, 5, 3, 1, 3, 1, 2, 5]
print(f"Input: {nums}")
print(f"Output: {frequency_sort(nums)}")
# Expected: [2, 5, 5, 3, 3, 1, 1, 1]
# Test Case 2: All same frequency
nums = [4, 2, 3, 1]
print(f"\nInput: {nums}")
print(f"Output: {frequency_sort(nums)}")
# Expected: [4, 3, 2, 1] (All freq=1, sort by value desc)
# Test Case 3: Negative numbers
nums = [-1, 1, -1, 2, -1, 3]
print(f"\nInput: {nums}")
print(f"Output: {frequency_sort(nums)}")
# -1:3, 1:1, 2:1, 3:1 → [3, 2, 1, -1, -1, -1]
# Test Case 4: Large numbers
nums = [100, 100, 200, 200, 200, 300]
print(f"\nInput: {nums}")
print(f"Output: {frequency_sort(nums)}")
# 100:2, 200:3, 300:1 → [300, 100, 100, 200, 200, 200]
ผลลัพธ์
Input: [1, 5, 3, 1, 3, 1, 2, 5] Output: [2, 5, 5, 3, 3, 1, 1, 1] Input: [4, 2, 3, 1] Output: [4, 3, 2, 1] Input: [-1, 1, -1, 2, -1, 3] Output: [3, 2, 1, -1, -1, -1] Input: [100, 100, 200, 200, 200, 300] Output: [300, 100, 100, 200, 200, 200]
วิธีอื่น: ใช้ Bucket Sort (O(n) Time)
def frequency_sort_bucket(nums):
"""ใช้ Bucket Sort - O(n) Time, O(n) Space"""
if not nums:
return []
freq = Counter(nums)
max_freq = max(freq.values())
# Buckets: Index = Frequency, Value = List of Numbers
buckets = [[] for _ in range(max_freq + 1)]
for num, f in freq.items():
buckets[f].append(num)
# เรียงในแต่ละ Bucket: Value Descending
for bucket in buckets:
bucket.sort(reverse=True)
# รวมผลลัพธ์: Frequency 1, 2, 3, ...
result = []
for f in range(1, max_freq + 1):
for num in buckets[f]:
result.extend([num] * f)
return result
# ทดสอบ
print(frequency_sort_bucket([1, 5, 3, 1, 3, 1, 2, 5])) # [2, 5, 5, 3, 3, 1, 1, 1]
Complexity Comparison
| Method | Time | Space | Note |
|---|---|---|---|
| sorted() + lambda | O(n log n) | O(n) | Simple, Pythonic |
| Bucket Sort | O(n) | O(n) | เร็วกว่าเมื่อ n ใหญ่, Max Freq ไม่ใหญ่เกินไป |
LeetCode Reference
Problem 1636: "Sort Array by Increasing Frequency" - Easy
