2023-8-30

8-30

数组

题号 剑指 Offer 45. 把数组排成最小的数

题目 输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

字符串 xy < yx , yz < zy ，需证明 xz < zx 一定成立。

设十进制数 x, y, z 分别有 a, b, c 位，则有：
（左边是字符串拼接，右边是十进制数计算，两者等价）
xy = x * 10^b + y 
yx = y * 10^a + x

则 xy < yx 可转化为：
x * 10^b + y < y * 10^a + x
x (10^b - 1) < y (10^a - 1)
x / (10^a - 1) < y / (10^b - 1)     ①

同理， 可将 yz < zy 转化为：
y / (10^b - 1) < z / (10^c - 1)     ②

将 ① ② 合并，整理得：
x / (10^a - 1) < y / (10^b - 1) < z / (10^c - 1)
x / (10^a - 1) < z / (10^c - 1)
x (10^c - 1) < z (10^a - 1)
x * 10^c + z < z * 10^a + x
∴  可推出 xz < zx ，传递性证毕

证明以上之后可以得到 xz<zx => x<z

后面使用快速排序

function minNumber(nums: number[]): string {
    const strs: string[] = nums.map(num => num.toString());  // 将数字转换为字符串
    quickSort(0, strs.length - 1, strs);  // 使用快速排序算法按照一定规则排序字符串
    return strs.join('');  // 拼接排序后的字符串，得到最小的字符串
}

 const quickSort = (l: number, r: number, strs: string[]): void => {
        if (l >= r) return;
        let i = l, j = r;
        while (i < j) {
            while (strs[j] + strs[l] >= strs[l] + strs[j] && i < j) j--;
            while (strs[i] + strs[l] <= strs[l] + strs[i] && i < j) i++;
            [strs[i], strs[j]] = [strs[j], strs[i]];
        }
        [strs[i], strs[l]] = [strs[l], strs[i]];
        quickSort(l, i - 1, strs);
        quickSort(i + 1, r, strs);
    };

这里学习了一下评论区的快排模版

function minNumber(nums: number[]): string {
    const quickSort = (strs: string[], low: number, high: number): void => {
        if (low < high) {
            const middle = getMiddle(strs, low, high);
            quickSort(strs, low, middle - 1);
            quickSort(strs, middle + 1, high);
        }
    };

    const getMiddle = (strs: string[], low: number, high: number): number => {
        const temp = strs[low];
        while (low < high) {
            while (low < high && (strs[high] + temp) >= (temp + strs[high])) high--;
            strs[low] = strs[high];
            while (low < high && (strs[low] + temp) <= (temp + strs[low])) low++;
            strs[high] = strs[low];
        }
        strs[low] = temp;
        return low;
    };

    const strs: string[] = nums.map(num => num.toString());
    quickSort(strs, 0, strs.length - 1);
    return strs.join('');
}

// 示例输入
const nums: number[] = [3, 30, 34, 5, 9];
console.log(minNumber(nums));  // 输出: "3033459"