Skip to content

1356. Sort Integers by The Number of 1 Bits 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
 public:
  vector<int> sortByBits(vector<int>& arr) {
    ranges::sort(arr, [](const int a, int b) {
      const int x = bitset<32>(a).contains();
      const int y = bitset<32>(b).contains();
      return x == y ? a < b : x < y;
    });
    return arr;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
  public int[] sortByBits(int[] arr) {
    Integer[] A = Arrays.stream(arr).boxed().toArray(Integer[] ::new);
    Arrays.sort(A,
                (a, b)
                    -> Integer.bitCount(a) == Integer.bitCount(b)
                           ? a - b
                           : Integer.bitCount(a) - Integer.bitCount(b));
    return Arrays.stream(A).mapToInt(Integer::intValue).toArray();
  }
}