🔗 🟢 1051. Height Checker 1303

tags: `Weekly Contest 138` `排序(Sorting)` `計數(Counting)` `計數排序(Counting Sort)` `前綴和(Prefix Sum)`

題意

給定一個整數陣列 $heights$ ， $heights[i]$ 表示第 $i$ 個學生的身高。

令 $expected$ 陣列表示學生按照 非遞減 的身高順序排列的預期身高。請注意，預期身高不一定是唯一的。

返回 $heights[i] \neq expected[i]$ 的索引數量。

約束條件

$1 \leq heights.length \leq 100$
$1 \leq heights[i] \leq 100$

思路

方法一：排序(Sorting)

按照題意，我們可以先將 $heights$ 進行排序後保存到另一個陣列 $expected$ 中，然後比較排序後的陣列和原陣列的差異，計算不同的元素個數即可。

複雜度分析

時間複雜度： $\mathcal{O}(n \log n)$ ，其中 $n$ 表示陣列 $heights$ 的長度。
空間複雜度： $\mathcal{O}(n)$ 。

class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        expected = sorted(heights)
        ans = 0
        for x, y in zip(heights, expected):
            ans += (x != y)
        return ans

class Solution {
public:
    int heightChecker(vector<int>& heights) {
        int n = heights.size();
        vector<int> expected = heights;
        sort(expected.begin(), expected.end());
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (heights[i] != expected[i]) {
                ans++;
            }
        }
        return ans;
    }
};

方法二：計數排序(Counting Sort)

注意到題目中身高的範圍在 $1$ 到 $100$ 之間，因此我們可以從值域的角度出發，使用計數排序(Counting Sort) 的方法來解決這個問題。計數排序是一種非比較排序算法，適用於元素範圍有限且範圍相對較小的情況。

對於值域中的每個數字 $x$ ，我們只要統計 $heights$ 陣列中值小於 $x$ 的數字個數 $s$ ，就可以得到 $x$ 在排序後的陣列中的位置。在排序後的陣列中， $expected[s], expected[s+1], \ldots, expected[s+cnt[x]-1]$ 這些位置上的元素都應該等於 $x$ 。而計算 $s$ 的過程可以使用前綴和(Prefix Sum) 來實現。

具體步驟如下：

創建一個大小為 $101$ 的計數數組 $cnt$ ，初始化為 $0$ ， $cnt[i]$ 表示身高為 $i$ 的學生數量。
遍歷 $heights$ 陣列，對每個學生的身高進行計數。
使用 $s$ 變量作為前綴和的起始位置，初始化為 $0$ 。
遍歷 $cnt$ 數組，檢查 $cnt[i]$ 的值，對於每個 $i$ ，遍歷 $s$ 到 $s+cnt[i]-1$ 的位置，檢查 $heights$ 陣列中相應位置的值是否和預期的身高 $i$ 一致。如果不一致，將 $ans$ 加 $1$ 。
將前綴和變量 $s$ 更新為當前處理身高的結束位置，準備處理下一個身高。
返回 $ans$ 。

複雜度分析

時間複雜度： $\mathcal{O}(D)$ ，其中 $D$ 表示值域的大小，本題中 $D = 101$ 。
空間複雜度： $\mathcal{O}(D)$ ， $cnt$ 陣列的大小與值域大小相同。

class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        cnt = [0] * 101
        for x in heights:
            cnt[x] += 1
        s = 0 # prefix sum
        ans = 0
        for i in range(101):
            for j in range(s, s + cnt[i]):
                if heights[j] != i:
                    ans += 1
            s += cnt[i]
        return ans

class Solution {
public:
    int heightChecker(vector<int>& heights) {
        int n = heights.size();
        vector<int> cnt(101, 0);
        for (int x : heights) cnt[x]++;
        int ans = 0, s = 0;
        for (int i = 0; i < 101; i++) {
            for (int j = 0; j < cnt[i]; j++) {
                if (heights[s++] != i) ans++;
            }
        }
        return ans;
    }
};