1356. Sort Integers by The Number of 1 Bits

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的數量一致的話,再依照其整數值做遞增排列。