最简单的网站代码,技术网站模版,在线生成app网站源码,受欢迎的菏泽网站建设问题背景
我们将整数 x x x 的 权重 定义为按照下述规则将 x x x 变成 1 1 1 所需要的步数#xff1a;
如果 x x x 是偶数#xff0c;那么 x x / 2 x x / 2 xx/2。如果 x x x 是奇数#xff0c;那么 x 3 x 1 x 3 \times x 1 x3x1。
比方说#xff0c; x …问题背景
我们将整数 x x x 的 权重 定义为按照下述规则将 x x x 变成 1 1 1 所需要的步数
如果 x x x 是偶数那么 x x / 2 x x / 2 xx/2。如果 x x x 是奇数那么 x 3 × x 1 x 3 \times x 1 x3×x1。
比方说 x 3 x 3 x3 的权重为 7 7 7。因为 3 3 3 需要 7 7 7 步变成 1 1 1 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 3 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 3→10→5→16→8→4→2→1。 给你三个整数 l o lo lo h i hi hi 和 k k k。你的任务是将区间 [ l o , h i ] [lo, hi] [lo,hi] 之间的整数按照它们的权重 升序排序 如果大于等于 2 2 2 个整数有 相同 的权重那么按照数字自身的数值 升序排序 。 请你返回区间 [ l o , h i ] [lo, hi] [lo,hi] 之间的整数按权重排序后的第 k k k 个数。 注意题目保证对于任意整数 x x x l o ≤ x ≤ h i lo \le x \le hi lo≤x≤hi 它变成 1 1 1 所需要的步数是一个 32 32 32 位有符号整数。
数据约束 1 ≤ l o ≤ h i ≤ 1000 1 \le lo \le hi \le 1000 1≤lo≤hi≤1000 1 ≤ k ≤ h i − l o 1 1 \le k \le hi - lo 1 1≤k≤hi−lo1
解题过程
这题的本质要求是将数组中的两个属性当作不同的标准完成二级排序。 刻画双重标准有两种做法一种是定义一个二维数组把数字和权重组成一个长为二的数对对这个数对进行排序另一种是用两个数组分别存储数字和权重存储权重的数组可以看作哈希表只作为标准来使用不参与排序。 从效率上来说第二种方法可以预处理计算所有可能的权重还可以避免重复后续重复计算之前已经得到的权重是更好的方法。实际上这题数据量不是很大选哪种方案都能搞定。
题目明确要求权重相同的按元素本身大小升序排列其实就是要求实际排序的流程是稳定的。 常见的排序算法包括 Java 本身提供的排序方法归并排序 这些当然都能解决问题。但如果进一步考虑到数据规模小计数排序 显然是最优的选择。
在这种情况下最好不要选择不稳定的算法。 题中要求第 K K K 大的数虽然使用非荷兰国旗问题的一般快排划分能够在 O ( N ) O(N) 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);}
}
