Leecode刷题C语言之将整数按权重排序

执行结果:通过

执行用时和内存消耗如下：

int getF(int x) {
    if (x == 1) {
        return 0;
    }
    if (x & 1) {
        return getF(x * 3 + 1) + 1;
    } else {
        return getF(x / 2) + 1;
    }
}

int compare(const void *a, const void *b) {
    int u = *(int*)a;
    int v = *(int*)b;
    int f1 = getF(u);
    int f2 = getF(v);
    if (f1 != f2) {
        return f1 - f2;
    }
    return u - v;
}

int getKth(int lo, int hi, int k) {
    int size = hi - lo + 1;
    int *v = (int *)malloc(size * sizeof(int));
    for (int i = 0; i < size; ++i) v[i] = lo + i;
    qsort(v, size, sizeof(int), compare);
    int res = v[k - 1];
    free(v);
    return res;
}

代码思路：

这段代码的主要思路是解决一个特定的问题：在一个给定的整数区间 [lo, hi] 内，找出经过特定变换后具有第 k 小变换次数的整数。这个特定变换基于著名的“3n+1 猜想”（也称为柯拉兹猜想）。下面是代码的详细思路：

1. getF(int x) 函数

这个函数计算一个整数 x 通过“3n+1 猜想”变换到 1 所需的步骤数。

• 递归终止条件：如果 x == 1，则不需要任何变换，返回 0。
• 奇数处理：如果 x 是奇数（x & 1 非零），则按照“3n+1 猜想”，x 变为 3x + 1，并递归计算新值的变换次数，最后加 1 表示当前这次变换。
• 偶数处理：如果 x 是偶数，则 x 变为 x / 2，并递归计算新值的变换次数，同样加 1 表示当前这次变换。

2. compare(const void *a, const void *b) 函数

这个函数用于比较两个整数 u 和 v，基于它们通过 getF 函数得到的变换次数。

• 首先，将 void 指针转换为 int 指针，然后解引用得到 u 和 v 的值。
• 调用 getF 函数计算 u 和 v 的变换次数 f1 和 f2。
• 如果 f1 和 f2 不相等，则根据变换次数进行升序排序（即返回 f1 - f2）。
• 如果 f1 和 f2 相等，则直接按 u 和 v 的值进行升序排序（即返回 u - v）。

3. getKth(int lo, int hi, int k) 函数

这个函数找出在区间 [lo, hi] 内，经过特定变换后具有第 k 小变换次数的整数。

• 首先，计算区间的大小 size。
• 动态分配一个整数数组 v，用于存储区间 [lo, hi] 内的所有整数。
• 使用循环将区间内的整数填充到数组 v 中。
• 使用 qsort 函数和自定义的比较函数 compare 对数组 v 进行排序。排序后的数组 v 按照变换次数升序排列，如果变换次数相同，则按整数值升序排列。
• 返回排序后数组中第 k 小的元素（注意数组索引从 0 开始，所以是 v[k - 1]）。
• 释放动态分配的内存。

总结

这段代码通过计算每个整数的“3n+1 猜想”变换次数，然后在给定的整数区间内找出具有第 k 小变换次数的整数。它首先定义了如何计算变换次数，然后定义了一个比较函数用于排序，最后实现了找出第 k 小变换次数整数的功能。