Question

1356. 根据数字二进制下 1 的数目排序

English Version

题目描述

给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。

如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。

请你返回排序后的数组。

 

示例 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 ，所以你需要按照数值大小将它们排序。

示例 3：

输入：arr = [10000,10000]
输出：[10000,10000]

示例 4：

输入：arr = [2,3,5,7,11,13,17,19]
输出：[2,3,5,17,7,11,13,19]

示例 5：

输入：arr = [10,100,1000,10000]
输出：[10,100,10000,1000]

 

提示：

• 1 <= arr.length <= 500
• 0 <= arr[i] <= 10^4

解法

方法一：自定义排序

我们将数组 $arr$ 按照题目要求排序，即按照二进制表示中数字 $1$ 的数目升序排序，如果存在多个数字二进制中 $1$ 的数目相同，则必须将它们按照数值大小升序排列。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $arr$ 的长度。

class Solution:
  def sortByBits(self, arr: List[int]) -> List[int]:
    return sorted(arr, key=lambda x: (x.bit_count(), x))

class Solution {
  public int[] sortByBits(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n; ++i) {
      arr[i] += Integer.bitCount(arr[i]) * 100000;
    }
    Arrays.sort(arr);
    for (int i = 0; i < n; ++i) {
      arr[i] %= 100000;
    }
    return arr;
  }
}

class Solution {
public:
  vector<int> sortByBits(vector<int>& arr) {
    for (int& v : arr) {
      v += __builtin_popcount(v) * 100000;
    }
    sort(arr.begin(), arr.end());
    for (int& v : arr) {
      v %= 100000;
    }
    return arr;
  }
};

func sortByBits(arr []int) []int {
  for i, v := range arr {
    arr[i] += bits.OnesCount(uint(v)) * 100000
  }
  sort.Ints(arr)
  for i := range arr {
    arr[i] %= 100000
  }
  return arr
}

function sortByBits(arr: number[]): number[] {
  const countOnes = (n: number) => {
    let res = 0;
    while (n) {
      n &= n - 1;
      res++;
    }
    return res;
  };
  return arr.sort((a, b) => countOnes(a) - countOnes(b) || a - b);
}

impl Solution {
  pub fn sort_by_bits(mut arr: Vec<i32>) -> Vec<i32> {
    arr.sort_by(|a, b| {
      let res = a.count_ones().cmp(&b.count_ones());
      if res == std::cmp::Ordering::Equal {
        return a.cmp(&b);
      }
      res
    });
    arr
  }
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int countOnes(int n) {
  int res = 0;
  while (n) {
    n &= n - 1;
    res++;
  }
  return res;
}

int cmp(const void* _a, const void* _b) {
  int a = *(int*) _a;
  int b = *(int*) _b;
  int res = countOnes(a) - countOnes(b);
  if (res == 0) {
    return a - b;
  }
  return res;
}

int* sortByBits(int* arr, int arrSize, int* returnSize) {
  qsort(arr, arrSize, sizeof(int), cmp);
  *returnSize = arrSize;
  return arr;
}

方法二

class Solution {
  public int[] sortByBits(int[] arr) {
    int n = arr.length;
    Integer[] t = new Integer[n];
    for (int i = 0; i < n; ++i) {
      t[i] = arr[i];
    }
    Arrays.sort(t, (a, b) -> {
      int x = Integer.bitCount(a), y = Integer.bitCount(b);
      return x == y ? a - b : x - y;
    });
    for (int i = 0; i < n; ++i) {
      arr[i] = t[i];
    }
    return arr;
  }
}

class Solution {
public:
  vector<int> sortByBits(vector<int>& arr) {
    sort(arr.begin(), arr.end(), [&](auto& a, auto& b) -> bool {
      int x = __builtin_popcount(a), y = __builtin_popcount(b);
      return x < y || (x == y && a < b);
    });
    return arr;
  }
};

func sortByBits(arr []int) []int {
  sort.Slice(arr, func(i, j int) bool {
    a, b := bits.OnesCount(uint(arr[i])), bits.OnesCount(uint(arr[j]))
    return a < b || (a == b && arr[i] < arr[j])
  })
  return arr
}