1356. Sort Integers by The Number of 1 Bits
一、題目
You are given an integer array arr
. Sort the integers in the array in ascending order by the number of 1
's in their binary representation and in case of two or more integers have the same number of 1
's you have to sort them in ascending order.
Return the array after sorting it.
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
二、程式作法
public class Solution
{
public int[] SortByBits(int[] arr)
{
int[] bits = new int[arr.Length];
for (int i = 0; i < arr.Length; i++)
{
int counter = 0;
int n = arr[i];
while (n > 0)
{
counter += n % 2;
n /= 2;
}
bits[i] = counter;
}
for (int i = 0; i < bits.Length - 1; i++)
{
int minIdx = i;
for (int j = i; j < bits.Length; j++)
{
if (bits[minIdx] > bits[j])
minIdx = j;
else if (bits[minIdx] == bits[j] && arr[minIdx] > arr[j])
minIdx = j;
}
int temp = bits[i];
bits[i] = bits[minIdx];
bits[minIdx] = temp;
temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
}
return arr;
}
}
三、思路筆記
題目要的是針對一個整數陣列,將每一個元素的二進制表示法之中含有1的數量,由小到大遞增排列,
並如果有兩個以上相同1的數量一致的話,再依照其整數值做遞增排列。