Kiểm Tra Chiều Cao (Height Checker) Trong Python

Học sinh phải xếp hàng theo chiều cao không giảm. Cho mảng heights chiều cao hiện tại. Trả về số học sinh không đứng đúng vị trí so với mảng đã sắp xếp.

Ví dụ: [1,1,4,2,1,3] → sắp xếp: [1,1,1,2,3,4] → 3 học sinh sai vị trí (4, 3, 1 cuối).

Thuật toán

1. Tạo bản sao đã sắp xếp: expected = sorted(heights)
2. Đếm số vị trí i mà heights[i] != expected[i]
3. Trả về đếm

Ví dụ (Python)

class Solution(object):
    def heightChecker(self, heights):
        expected = sorted(heights)
        return sum(1 for i, h in enumerate(heights) if h != expected[i])

ob1 = Solution()
print(ob1.heightChecker([1,1,4,2,1,3]))  # 3
print(ob1.heightChecker([5,1,2,3,4]))    # 5
print(ob1.heightChecker([1,2,3,4,5]))    # 0

Độ phức tạp

• Thời gian: O(n log n) (do sort)
• Không gian: O(n) (mảng sorted)

Tối ưu O(n) nếu chiều cao giới hạn (ví dụ 1-100): dùng Counting Sort.

def heightChecker(heights):
    freq = [0] * 101
    for h in heights:
        freq[h] += 1
    
    expected = []
    for h in range(101):
        expected.extend([h] * freq[h])
    
    return sum(1 for i, h in enumerate(heights) if h != expected[i])

Đầu vào / Đầu ra

Input:  [1,1,4,2,1,3]
Output: 3