題目會給定我們一個n值,要求我們列出從0 ~ n 之間,每個整數有幾個bit1,以陣列的形式返回答案。
例如n=3時
因為
0 = 0b 0
1 = 0b 1
2 = 0b 10
3 = 0b 11
輸出答案為[0, 1, 1, 2]
Example 1:
Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10
Example 2:
Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
Constraints:
0 <= n <= 10^5
輸入n值介於 0 ~ 十萬之間。
Follow up:
O(n log n)
. Can you do it in linear time O(n)
and possibly in a single pass?很容易有一個直覺的解法是暴力掃描過每個整數的每個bit,複雜度為O( n log n)。
請問您能想到一個O(n)的演算法嗎?
__builtin_popcount
in C++)?請問您能不要使用內建的數bit function嗎?