将整数按权排序

将整数按权排序(medium)

做题过程

按照模拟的思路用哈希表计算步骤并存储，之后自定义比较器进行排序，直接对整理好的列表随机访问即可。

算法概述

本题要求为计算每个元素通过一些操作变为1的过程中所需的操作数，并按照升序排列，再返回第k个排序后的元素。可以采用 记忆化搜索 进行剪枝。

时间复杂度为O(c)：经过记忆化搜索平摊排序时间，在最坏情况下仍可变为常数级
空间复杂度为O(2)：记忆化搜索维护的哈希表是动态变化的，空间存储也可以随着目标数组的长度不断分摊，变为常数级

JAVA

class Solution {
    Map<Integer, Integer> f = new HashMap<Integer, Integer>();

    public int getKth(int lo, int hi, int k) {
        List<Integer> list = new ArrayList<Integer>();
        for (int i = lo; i <= hi; ++i) {
            list.add(i);
        }
        Collections.sort(list, new Comparator<Integer>() {
            public int compare(Integer u, Integer v) {
                if (getF(u) != getF(v)) {
                    return getF(u) - getF(v);
                } else {
                    return u - v;
                }
            }
        });
        return list.get(k - 1);
    }

    public int getF(int x) {
        // 记忆化搜索
        if (!f.containsKey(x)) {
            if (x == 1) {
                f.put(x, 0);
            } else if ((x & 1) != 0) {
                f.put(x, getF(x * 3 + 1) + 1);
            } else {
                f.put(x, getF(x / 2) + 1);
            }
        }
        return f.get(x);
    }
}

总结

我还用到了哈希表和更复杂的自定义数据结构，但实际上完全没有必要，应该像上述题解一样把记忆化搜索的操作放在 分装的函数 中，而主函数内部应该是简洁的，这才是正确规划代码结构的思维。