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

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

• Hash

function sortByBits(arr: number[]): number[] {
    const bitsMap: Map<number, number> = makeMap(arr);
    return arr.sort((a, b) => bitsMap.get(a) === bitsMap.get(b) ? a - b : bitsMap.get(a) - bitsMap.get(b));
};

function makeMap(array: number[]): Map<number, number> {
    const map: Map<number, number> = new Map<number, number>();
    for (const num of array) {
        !map.has(num) && map.set(num, getOneTimes(num));
    }
    return map;
}
// 给我一个数字,我可以告诉你它里面有多少个1
function getOneTimes(num: number): number {
    let count: number = 0;
    while (num) {
        num &= (num - 1);
        ++count;
    }
    return count;
}

• 记忆化

    // TODO: 有空练习一下就行,详解在官方题解