前往
大廳
主題

LeetCode - 1356. Sort Integers by The Number of 1 Bits 解題心得

Not In My Back Yard | 2022-10-24 12:00:03 | 巴幣 0 | 人氣 133

題目連結:


題目意譯:
你被給定一整數陣列 arr。將陣列中的整數們按照它們二進位表示法中 1 的個數由少排到多,如果有一樣數量的則按本來的數值由小到大排。

回傳排序後的陣列。

限制:
1 ≦ arr.length ≦ 500
0 ≦ arr[i] ≦ 10 ^ 4



範例測資:
範例 1:
輸入: arr = [0,1,2,3,4,5,6,7,8]
輸出: [0,1,2,4,8,3,5,6,7]
解釋: [0] 為唯一一個有著 0 個 1 的整數。
[1,2,4,8] 都有 1 個 1。
[3,5,6] 有 2 個 1。
[7] 有 3 個 1。
根據 1 之位元數排序後的陣列為 [0,1,2,4,8,3,5,6,7]

範例 2:
輸入: arr = [1024,512,256,128,64,32,16,8,4,2,1]
輸出: [1,2,4,8,16,32,64,128,256,512,1024]
解釋: 所有整數在二進位表示法中都有著 1 個 1,因此將它們按升序排序即可。


解題思維:
又是一題自定義排序的問題(如這題),可以先行把每個數字在二進位表示法中 1 的個數算出來(全域地預先建表也可以,如這題的建表方式)然後寫一個呼叫排序函式時要用的比較函式即可。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作