LeetCode 338. 比特位計數：O(n) 時間複雜度的動態規劃解法

LeetCode 338. 比特位計數

給定一個非負整數 num，對於範圍 0 ≤ i ≤ num 中的每個數字 i，計算其二進制表示中 1 的個數，並將結果作為陣列返回。

範例

輸入：num = 5
輸出：[0,1,1,2,1,2]

進階挑戰

• 很容易想到 O(n * sizeof(integer)) 的解法，但能否在線性時間 O(n) 內完成？
• 空間複雜度應為 O(n)。
• 能否不使用任何內建函數（如 C++ 的 __builtin_popcount）來實現？

核心思路：動態規劃與位運算

觀察二進制規律：對於任意整數 i，其最高有效位之前的部分與 i & (i-1) 相同。i & (i-1) 操作會清除最低位的 1。因此，i 中 1 的個數等於 i & (i-1) 中 1 的個數加 1。

遞推公式：count[i] = count[i & (i-1)] + 1，初始條件 count[0] = 0。

C 語言實現

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* countBits(int num, int* returnSize) {
    int *ary = (int *)malloc((num + 1) * sizeof(int));
    ary[0] = 0;
    for (int i = 1; i <= num; i++) {
        ary[i] = ary[i & (i - 1)] + 1;
    }
    *returnSize = num + 1;
    return ary;
}

複雜度分析

• 時間複雜度：O(n)，每個數字只需常數時間計算。
• 空間複雜度：O(n)，用於存儲結果陣列。

總結

利用 i & (i-1) 消除最低位 1 的特性，將問題轉化為已解決的子問題，實現了線性時間解法，且不依賴任何內建函數。