【Leetcode 每日一题】1387. 将整数按权重排序

问题背景

我们将整数 $x$ 的 权重 定义为按照下述规则将 $x$ 变成 $1$ 所需要的步数：

• 如果 $x$ 是偶数，那么 $x=x/2$。
• 如果 $x$ 是奇数，那么 $x=3\times x+1$。

比方说，$x=3$ 的权重为 $7$。因为 $3$ 需要 $7$ 步变成 $1$（$3\to 10\to 5\to 16\to 8\to 4\to 2\to 1$）。
给你三个整数 $lo$，$hi$ 和 $k$。你的任务是将区间 $[lo,hi]$ 之间的整数按照它们的权重 升序排序 ，如果大于等于 $2$ 个整数有 相同 的权重，那么按照数字自身的数值 升序排序 。
请你返回区间 $[lo,hi]$ 之间的整数按权重排序后的第 $k$ 个数。
注意，题目保证对于任意整数 $x$（$lo\le x\le hi$） ，它变成 $1$ 所需要的步数是一个 $32$ 位有符号整数。

数据约束

• $1\le lo\le hi\le 1000$
• $1\le k\le hi-lo+1$

解题过程

这题的本质要求是将数组中的两个属性当作不同的标准，完成二级排序。
刻画双重标准有两种做法，一种是定义一个二维数组，把数字和权重组成一个长为二的数对，对这个数对进行排序；另一种是用两个数组分别存储数字和权重，存储权重的数组可以看作哈希表，只作为标准来使用，不参与排序。
从效率上来说，第二种方法可以预处理计算所有可能的权重，还可以避免重复后续重复计算之前已经得到的权重，是更好的方法。实际上这题数据量不是很大，选哪种方案都能搞定。

题目明确要求权重相同的按元素本身大小升序排列，其实就是要求实际排序的流程是稳定的。
常见的排序算法，包括 Java 本身提供的排序方法，归并排序 这些当然都能解决问题。但如果进一步考虑到数据规模小，计数排序 显然是最优的选择。

在这种情况下，最好不要选择不稳定的算法。
题中要求第 $K$ 大的数，虽然使用非荷兰国旗问题的一般快排划分，能够在 $O(N)$ 这个量级的时间下得到结果，但实际上完全没必要（仅考虑本题的话，有计数排序兜底）。
我也尝试实现了随机快排和堆排，发现要将不稳定的排序算法改造成能按多个标准排序是比较麻烦的，浪费了相当多的时间。
几分钟就做完的题，尝试改算法改了一上午还没成功，还是不折磨自己了，今天是讨厌快排的一天。

具体实现

调用 API

class Solution {private static final int MAX_N = 1010;private static final int[] memo = new int[MAX_N];public int getKth(int lo, int hi, int k) {int n = hi - lo + 1;        for(int i = 0; i < n; i++) {int curIndex = i + lo;memo[curIndex] = memo[curIndex] != 0 ? memo[curIndex] : calcWeight(curIndex);}Integer[] nums = new Integer[n];Arrays.setAll(nums, i -> i + lo);Arrays.sort(nums, (o1, o2) -> memo[o1] != memo[o2] ? memo[o1] - memo[o2] : o1 - o2);return nums[k - 1];}private int calcWeight(int n) {int res = 0;while(n != 1) {if((n & 1) == 1) {n = 3 * n + 1;} else {n >>>= 1;}res++;}return res;}
}

归并排序

class Solution {private static final int MAX_N = 1010;private static final int[] memo = new int[MAX_N];private static final int[] temp = new int[MAX_N];public int getKth(int lo, int hi, int k) {int n = hi - lo + 1;        for(int i = 0; i < n; i++) {int curIndex = i + lo;memo[curIndex] = memo[curIndex] != 0 ? memo[curIndex] : calcWeight(curIndex);}int[] nums = new int[n];Arrays.setAll(nums, i -> i + lo);mergeSort(nums, 0, n - 1);return nums[k - 1];}private int calcWeight(int n) {int res = 0;while(n != 1) {if((n & 1) == 1) {n = 3 * n + 1;} else {n >>>= 1;}res++;}return res;}private void merge(int[] arr, int left, int mid, int right) {int index1 = left, index2 = mid + 1, index = left;while(index1 <= mid && index2 <= right) {temp[index++] = memo[arr[index1]] <= memo[arr[index2]] ? arr[index1++] : arr[index2++];}while(index1 <= mid) {temp[index++] = arr[index1++];}while(index2 <= right) {temp[index++] = arr[index2++];}System.arraycopy(temp, left, arr, left, right - left + 1);}private void mergeSort(int[] arr, int left, int right) {if(left == right) {return;}int mid = left + ((right - left) >>> 1);mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);merge(arr, left, mid, right);}
}

计数排序

class Solution {private static final int MAX_N = 1010;private static final int[] memo = new int[MAX_N];public int getKth(int lo, int hi, int k) {int n = hi - lo + 1;        for(int i = 0; i < n; i++) {int curIndex = i + lo;memo[curIndex] = memo[curIndex] != 0 ? memo[curIndex] : calcWeight(curIndex);}int[] nums = new int[n];Arrays.setAll(nums, i -> i + lo);countingSort(nums);return nums[k - 1];}private int calcWeight(int n) {int res = 0;while(n != 1) {if((n & 1) == 1) {n = 3 * n + 1;} else {n >>>= 1;}res++;}return res;}private void countingSort(int[] arr) {int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;for(int item : arr) {min = Math.min(min, memo[item]);max = Math.max(max, memo[item]);}int range = max - min + 1;int[] count = new int[range];for(int item : arr) {count[memo[item] - min]++;}for(int i = 1; i < count.length; i++) {count[i] += count[i - 1];}int[] res = new int[arr.length];for(int i = arr.length - 1; i >= 0; i--) {int cur = arr[i];res[--count[memo[cur] - min]] = cur;}System.arraycopy(res, 0, arr, 0, arr.length);}
}