題目敘述
題目會給定一個存有整數的陣列，要求我們依照下列規則進行排序，由小排到大，升序排列。
規則:
bit1 數目多的大於bit1數目少的。若兩個整數bit1數目一樣多，則原本整數比較大的勝出。
測試範例
Example 1:
Input: arr = [0,1,2,3,4,5,6,7,8]
Output: [0,1,2,4,8,3,5,6,7]
Explantion: [0] is the only integer with 0 bits.
[1,2,4,8] all have 1 bit.
[3,5,6] have 2 bits.
[7] has 3 bits.
The sorted array by bits is [0,1,2,4,8,3,5,6,7]
Example 2:
Input: arr = [1024,512,256,128,64,32,16,8,4,2,1]
Output: [1,2,4,8,16,32,64,128,256,512,1024]
Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.
約束條件
Constraints:
1 <= arr.length <= 5000 <= arr[i] <= 104
演算法
依照規則，進行客製化排序，升序排列即可。
- 先依照bit 1的數目排序。
- 若bit 1的數目平手，再依照原本整數的大小排序。
程式碼
class Solution:
def sortByBits(self, arr: List[int]) -> List[int]:
return sorted(arr, key = lambda x : ( bin(x)[2:].count('1'), x) )
複雜度分析
時間複雜度:
O( n log n ) 標準排序演算法所付出的時間成本。
空間複雜度:
O( n ) 中間為了排序所產生的temp array和原本的輸入陣列一樣長。
關鍵知識點
基本上不難，以python的視角來看，關鍵是要熟悉lambda function、binary string bin()、和 out-of-place sorting sorted()的語法。
Reference:
