JavaScript / TypeScript / PHP / GO / Python / C / C++ / C# / Java 自定义排序 + 位运算 / 字母哈希映射:求解《1356. 根据数字二进制下 1 的数目排序》

2022-06-26 18:06:56
JavaScript / TypeScript / PHP / GO / Python / C / C++ / C# / Java 自定义排序 + 位运算 / 字母哈希映射,求解《1356. 根据数字二进制下 1 的数目排序》

例题

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

给你一个整数数组 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]

答案

自定义排序 · 位运算
var sortByBits = function(arr) {
  return arr.sort((a, b) => count1(a) - count1(b) || a - b)
};
const count1 = n => {
  let r = 0
  while (n) {
    r++
    n &= n - 1
  }
  return r
}
自定义排序 · 哈希映射(小写字母)

function sortByBits(arr: number[]): number[] {
  const h = new Uint8Array(10001)
  for (let i = 1; i <= 10000; i++) h[i] = h[i >> 1] + (i & 1)
  return arr.sort((a, b) => h[a] - h[b] || a - b)
};
class Solution {
  function sortByBits($arr) {
    $h = array_fill(0, 10001, 0);
    for ($i = 1; $i <= 10000; $i++) $h[$i] = $h[$i >> 1] + ($i & 1);
    usort($arr, function($a, $b) use(&$h) {
      $t = $h[$a] - $h[$b];
      return $t === 0 ? $a > $b : $t;
    });
    return $arr;
  }
}
func sortByBits(arr []int) []int {
  h := make([]int, 10001)
  for i := 1; i <= 10000; i++ {
    h[i] = h[i >> 1] + i & 1
  }
  sort.SliceStable(arr, func(i, j int) bool {
    t := h[arr[i]] - h[arr[j]]
    if t == 0 {
      return arr[i] < arr[j]
    }
    return  t < 0
  })
  return arr
}
class Solution:
  def sortByBits(self, arr: List[int]) -> List[int]:
    h = [0] * 10001
    for i in range(1, 10001): h[i] = h[i >> 1] + (i & 1)
    return sorted(arr, key = lambda x : (h[x], x))
class Solution {
  public int[] sortByBits(int[] arr) {
    int n = arr.length;
    int[] h = new int[10001];
    for (int i = 1; i <= 10000; i++) {
      h[i] = h[i >> 1] + (i & 1);
    }
    Integer[] nums = new Integer[n];
    for (int i = 0; i < n; i++) {
      nums[i] = arr[i];
    }
    Arrays.sort(nums, (a, b) -> {
      int t = h[a] - h[b];
      return t == 0 ? a - b : t;
    });
    for (int i = 0; i < n; i++) {
      arr[i] = nums[i];
    }
    return arr;
  }
}
public class Solution {
  public int[] SortByBits(int[] arr) {
    int[] h = new int[10001];
    for (int i = 1; i <= 10000; i++) {
      h[i] = h[i >> 1] + (i & 1);
    }
    Array.Sort(arr, delegate(int a, int b) {
      int t = h[a] - h[b];
      return t == 0 ? a - b : t;
    });
    return arr;
  }
}
int* sortByBits(int* arr, int arrSize, int* returnSize){
  int* h = (int *)malloc(sizeof(int) * 10001);
  h[0] = 0;
  int cmp (const void * a, const void * b) {
    int t = h[*(int*)a] - h[*(int*)b];
    return t == 0 ? *(int*)a - *(int*)b : t;
  }
  for (int i = 1; i <= 10000; i++) {
    h[i] = h[i >> 1] + (i & 1);
  }
  qsort(arr, arrSize, sizeof(int), cmp);
  *returnSize = arrSize;
  return arr;
}
class Solution {
public:
  vector<int> sortByBits(vector<int>& arr) {
    int h[10001];
    for (int i = 0; i < 10001; i++) {
      h[i] = h[i >> 1] + (i & 1);
    }
    sort(arr.begin(), arr.end(), [&] (int a, int b) {
      int t = h[a] - h[b];
      return t == 0 ? a < b : t < 0;
    });
    return arr;
  }
};

代码
奇数筛(位运算) + 阶乘 + 排列:求解《204. 计数质数》和《1175. 质数排列》
奇数筛(位运算) + 阶乘 + 排列,求解《204. 计数质数》和《1175. 质数排列》
代码
哈希集合 + 哈希映射 + 随机数生成:求解《217. 存在重复元素》《242. 有效的字母异位词》和《710. 黑名单中的随机数》
哈希集合 + 哈希映射 + 随机数生成,求解《217. 存在重复元素》《242. 有效的字母异位词》和《710. 黑名单中的随机数》
代码
哈希映射 + 滑动窗口:求解《438. 找到字符串中所有字母异位词》和《30. 串联所有单词的子串》
哈希映射 + 滑动窗口,求解《438. 找到字符串中所有字母异位词》和《30. 串联所有单词的子串》