【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);
    }
}