LeetCode 1387.将整数按权重排序

题目

题目链接

示例：

输入：lo = 12, hi = 15, k = 2
输出：13
解释：12 的权重为 9（12 --> 6 --> 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1）
13 的权重为 9
14 的权重为 17
15 的权重为 17
区间内的数按权重排序以后的结果为 [12,13,14,15] 。对于 k = 2 ，答案是第二个整数也就是 13 。
注意，12 和 13 有相同的权重，所以我们按照它们本身升序排序。14 和 15 同理。

题目分析

题目给定我们一种求权重的方式，然后要我们按照将给定范围内的数字按照权重排序，如果权重相同，则按照数值大小排序。

我们首先设置一个结构体分别储存数值和权重:

typedef struct {
    int val;
    int pow;
} P;

然后从lo遍历到hi，对每个数字求权重，将其插入结构体数组：

int num = hi - lo + 1;
P* arr = (P*)calloc(num, sizeof(P));
for (int i = 0; i < num; i++) {
    arr[i].val = lo;
    arr[i].pow = getpow(lo);
    lo++;
}

然后用排序，需要额外处理的地方是权重相同时按照数值大小排序，我们对Parition函数做一些小改动就可以实现这样的功能，这里以Parition函数的一部分来举例：

while (low < high) {
    if (arr[high].pow > pivot.pow) {
        high--;
    }else if (arr[high].pow == pivot.pow) {
        // 如果权重相同，比数值
        if (arr[high].val >= pivot.val) high--;
        else {
            arr[low] = arr[high];
            break;
        }
    }else {
        arr[low] = arr[high];
        break;
    }
}

最后输出arr[k - 1]即可。完整结果见最后。

题目解答

typedef struct {
    int val;
    int pow;
} P;

int getpow(int n) {
    int count = 0;
    while (n != 1) {
        if (n % 2 == 0) {
            n = n / 2;
        }else n = 3 * n + 1;
        count++;
    }
    return count;
}

void swap(P* arr, int i, int j) {
    P temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

int Parition(P* arr, int low, int high) {
    P pivot = arr[low];
    while (low < high) {
        while (low < high) {
            if (arr[high].pow > pivot.pow) {
                high--;
            }else if (arr[high].pow == pivot.pow) {
                if (arr[high].val >= pivot.val) high--;
                else {
                    arr[low] = arr[high];
                    break;
                }
            }else {
                arr[low] = arr[high];
                break;
            }
        }
        while (low < high) {
            if (arr[low].pow < pivot.pow) {
                low++;
            }else if (arr[low].pow == pivot.pow){
                if (arr[low].val <= pivot.val) low++;
                else {
                    arr[high] = arr[low];
                    break;
                }
            }
            else {
                arr[high] = arr[low];
                break;
            }
        }
    }
    arr[low] = pivot;
    return low;
}

void QuickSort(P* arr, int low, int high) {
    if (low < high) {
        int p = Parition(arr, low, high);
        QuickSort(arr, low, p - 1);
        QuickSort(arr, p + 1, high);
    }
}

int getKth(int lo, int hi, int k){
    int num = hi - lo + 1;
    P* arr = (P*)calloc(num, sizeof(P));

    for (int i = 0; i < num; i++) {
        arr[i].val = lo;
        arr[i].pow = getpow(lo);
        lo++;
    }

    QuickSort(arr, 0, num - 1);

    return arr[k - 1].val;
}