排序應用題 Sort Integers by The Number of 1 Bits Leetcode #1356

Alexander Sinn on Unsplash

題目敘述

題目會給定一個存有整數的陣列，要求我們依照下列規則進行排序，由小排到大，升序排列。

規則:

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 <= 500
• 0 <= arr[i] <= 104

演算法

依照規則，進行客製化排序，升序排列即可。

1. 先依照bit 1的數目排序。
2. 若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:

[1] Python sol. by customized lambda 90%+ [with Hint and Explanation] - Sort Integers by The Number of 1 Bits - LeetCode