文档教程知识库【免费下载链接】algorithm-base一位酷爱做饭的程序员立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址https://gitcode.com/gh_mirrors/al/algorithm-base点击查看免费下载本篇技术指南以 algorithm-base 仓库《数据结构和算法》目录中的经典题解为主体系统讲解两道互为镜像的拼数题剑指 Offer 45 把数组排成最小的数、LeetCode 179 最大数如何把求拼接最小数这一看似需要全排列的难题转化为一次基于自定义比较规则的排序并从数学上严格证明该规则的完备性自反、对称、传递与正确性排序结果即最小数。读者读完后既能完整掌握该题的证明脉络也能理解仓库反复使用的三向切分Three-Way Partition快速排序在排序类问题中的实战写法。一、问题引入两道互为镜像的拼数题本文讨论的两个题目根源上都是排序问题原文档在开篇就点名了它们剑指 Offer 45. 把数组排成最小的数LeetCode 179. 最大数先看剑指 Offer 45 的题目描述输入一个非负整数数组把数组里所有数字拼接起来排成一个数打印能拼接出的所有数字中最小的一个。示例 1输入: [10,2] 输出: 102示例 2输入: [3,30,34,5,9] 输出: 3033459题目很容易理解就是让我们找出拼接的所有数字中最小的一个。这里有一个容易被忽略的细节因为拼接结果可能非常大我们不能返回 int 类型而是应该把数字转换成字符串后拼接返回所以这类问题本质上是隐形的大数问题。这一点也是后续代码中第一步就把int[]转成String[]的根本原因。LeetCode 179 最大数则是它的镜像题把数组里所有数字拼接起来排成一个数打印能拼接出的所有数字中最大的一个。两题只有求最小与求最大之差解题框架完全一致本文会在最后给出改编要点。二、朴素思路与瓶颈全排列的 n! 灾难看到打印能拼接出的所有数字中最小的一个最容易想到的解题思路是先求出数组中所有数字的全排列把每个排列依次拼接成字符串最后从所有结果中取出最小值。这个思路在数学上正确但工程上完全不可行数组共有 n 个数则有n! 个排列当 n 稍大如 n 1212! ≈ 4.79 亿时枚举量已经难以承受。显然我们需要更高效的方法——把枚举所有排列降维成一次排序。那么问题来了排序需要定义元素之间的大小关系而这里两个数字拼起来谁大谁小取决于拼接顺序。于是我们引出本文的核心自定义一套比较规则。三、核心思路定义拼接序这一新比较规则假设两个数字 m、n可以拼接成mn和nm那么我们怎么返回最小的那个数字呢我们需要比较mn和nm假设mn nm此时求得的最小数字就是mn因为在最小数字mn中m 排在 n 的前面我们此时定义 m小于n。注mn代表 m 和 n 进行拼接例如 m 10, n 1mn 101。特别注意这里的小于并不是数值意义上的而是我们自己定义的规则——因为在最小数字mn中 m 位于 n 的前面所以我们定义 m 小于 n。下面通过一个例子加深理解。假设 m 10n 1则有mn 101 和nm 110比较 101 和 110发现 101 110所以此时的最小数字为 101又因为在最小数字中 10m排在 1n的前面根据定义10小于1反之 1 大于 10。到这里我们定义了一种新的、比较两个数字大小的规则。但马上要回答一个关键问题怎么保证这种规则是有效的换言之怎么确保通过这种规则对数组中所有数字而不只是两个数字排序后拼接得到的数就是最小的要回答这个问题需要两轮数学证明先证明规则本身有效满足自反性、对称性、传递性构成一个可排序的全序关系再证明按规则排序的结果 最小拼接数用反证法。四、规则有效性证明它构成全序关系为了便于分辨我们用 A、B、C 表示元素用 a、b、c 表示元素用十进制表示时的位数。分三步证明。1. 自反性AA AA所以A 等于 A。自反性显然成立。2. 对称性如果 A小于B则AB BA所以BA AB即B 大于 A。对称性成立。3. 传递性证明稍微复杂值得认真阅读传递性是指如果 A 小于 B且 B 小于 C则 A 小于 C。如果 A 小于 B则AB BA。假设 A 和 B 用十进制表示时分别有 a 位和 b 位则拼接可以写成AB A × 10^b B BA B × 10^a A例A 10a 2两位数B 1b 1一位数AB A × 10^b B 10 × 10^1 1 101BA B × 10^a A 1 × 10^2 10 110由AB BA即A × 10^b B B × 10^a A整理得A / (10^a - 1) B / (10^b - 1)同理如果 B 小于 C则BC CB。设 C 用十进制表示时有 c 位与前面推导过程完全一样BC B × 10^c C CB C × 10^b B由BC CB整理得B / (10^b - 1) C / (10^c - 1)把两个不等式串联起来A / (10^a - 1) B / (10^b - 1) C / (10^c - 1)于是得到A / (10^a - 1) C / (10^c - 1)逆推回去即AC CA也就是A 小于 C。传递性证得。通过上面的证明过程我们定义的规则满足自反性、对称性、传递性说明规则本身是有效的可以放心地把它当作排序的比较函数来用。五、为什么排序结果一定是最小值反证法规则有效只说明能排出一个稳定有序的序列还不能说明排出来的序列拼接后就是最小值。接下来用反证法完成这最后一公里证明。先回顾一下我们定义的规则当mn nm时得到最小数字mn。因为在最小数字mn中m 排在 n 的前面我们此时定义 m 小于 n。现在假设我们根据上述规则排序得到的数字为xxxxxxxx但存在这么一对字符串 A、B虽然AB BA按规则 A 应该排在 B 的前面然而在最后结果中A 却排在 B 的后面。此时所有可能的情况可以归结为两大类B 和 A 之间没有其他值A、B 相邻B 和 A 之间有其他值。情况一B 和 A 之间没有其他值相邻假设我们求得的最小值为XXXXBA——虽然 A 小于 B但在最后结果中 B 排在了 A 的前面这和我们定义的规则冲突。那么问题来了这个值是最小值吗假设XXXXBA为最小值。但是因为 A 小于 B所以AB BA那么XXXXAB XXXXBA即XXXXAB一定小于XXXXBA与我们XXXXBA是最小值的假设矛盾。BAXXXX的情况同理可证。情况二B 和 A 之间有其他值非相邻即形如BXXXXA。我们可以将中间的XXXX看成一个字符串 C于是整个结果记为BCA。因为求得的最小值为 BCA在最小值 BCA 中B 在 C 的前面C 在 A 的前面若相邻位置违反规则交换相邻元素即可得到更小的数因此在最小值中相邻元素必然满足规则BC CB即 B 小于 CCA AC即 C 小于 A根据上一节已经证明的传递性由 B 小于 C、C 小于 A 可得B 小于 A。但是我们一开始假设的是 A 小于 B与假设冲突证得该情况同样不可能出现。结论综上所述假设不成立从而得出结论对于排成的最小数字不存在满足下述关系的一对字符串虽然 A 小于 B但是在最后结果中 B 排在了 A 的前面。也就是说按自定义规则排序得到的结果与最小拼接数所要求的顺序完全一致——排序即答案。六、代码实现用三向切分完成排序规则证明完毕接下来直接看代码。原文档给出的解法正是仓库在 快速排序.md 中重点介绍过的三向切分Three-Way Partition它特别适合处理存在大量相等元素的排序场景——在本问题中相等即mn nm如 3 与 33 这类数字。Java 版class Solution { public String minNumber(int[] nums) { String[] arr new String[nums.length]; //解决大数问题将数字转换为字符串 for (int i 0 ; i nums.length; i) { arr[i] String.valueOf(nums[i]); } quickSort(arr,0,arr.length-1); StringBuffer str new StringBuffer(); for (String x : arr) { str.append(x); } return str.toString(); } public void quickSort(String[] arr, int left, int right) { if (left right) { return; } int low left; int high right; int i low1; String pivot arr[low]; while (i high) { //比较大小 if ((pivotarr[i]).compareTo(arr[i]pivot) 0 ) { swap(arr,i,low); } else if ((pivotarr[i]).compareTo(arr[i]pivot) 0) { swap(arr,i,high--); } else { i; } } quickSort(arr,left,low-1); quickSort(arr,high1,right); } public void swap(String[] arr, int i, int j) { String temp arr[i]; arr[i] arr[j]; arr[j] temp; } }Python 版from typing import List class Solution: def minNumber(self, nums: List[int])-str: arr [] * len(nums) # 解决大数问题将数字转换为字符串 for i in range(0, len(nums)): arr[i] str(nums[i]) self.quickSort(arr, 0, len(arr) - 1) s for x in arr: s x return s def quickSort(self, arr: List[str], left: int, right: int): if left right: return low left high right i low 1 pivot arr[low] while i high: # 比较大小 if int(pivot arr[i]) int(arr[i] pivot): self.swap(arr, i, low) i 1 low 1 elif int(pivot arr[i]) int(arr[i] pivot): self.swap(arr, i, high) high - 1 else: i 1 self.quickSort(arr, left, low - 1) self.quickSort(arr, high 1, right) def swap(self, arr: List[str], i: int, j: int): temp arr[i] arr[i] arr[j] arr[j] temp代码逐行解读这段代码本质上是把pivot取区间第一个元素当作中间值一趟循环把数组分成三块小于 pivot 的左区、等于 pivot 的中区、大于 pivot 的右区。对照三向切分的指针语义逐行看low指向等于区间的左边界high指向等于区间的右边界i是探路指针当(pivotarr[i]).compareTo(arr[i]pivot) 0即arr[i] pivot pivot arr[i]说明arr[i] 小于 pivot应该放到左区执行swap(arr, i, low)当比较结果 0说明arr[i] 大于 pivot应该放到右区执行swap(arr, i, high--)——注意此时不移动 i因为交换过来的元素大小未知需要下一轮继续判断当比较结果 0说明 arr[i] 等于 pivot属于中区仅i。一趟结束后等于 pivot 的中区正好落在[low, high]递归只处理左右两个小区间[left, low-1]与[high1, right]中间的相等元素不再参与后续排序——这正是三向切分能大幅缩小递归区间的原因。关于比较函数还有一个值得注意的技术细节mn与nm的位数总是相同的都等于 m 的位数加 n 的位数因此对它们做字符串字典序比较等价于数值比较。这就是 Java 版可以直接使用String.compareTo而非转成 int/BigInteger的原因Python 版虽然用int()显式转换以对齐数值语义但两种写法在正确性上是等价的。七、原理纵深三向切分、荷兰国旗与快速排序优化理解了上面的代码你会发现它与仓库中另外两篇文档的技术内核完全同源值得放在一起读形成知识网络。1. 三向切分的基本原理在 快速排序.md 中作者用探路指针 i形象地剖析了三向切分我们利用探路指针也就是 i遇到比 pivot 大的元素则和 right 指针进行交换此时 right 指向的元素肯定比 pivot 大则 right--但是此时我们的 nums[i] 指向的元素并不知道情况所以我们的 i 指针不动如果此时 nums[i] pivot 则与 left 指针交换注意此时我们的 left 指向的值肯定是等于 pivot 的所以交换后我们要 left, inums[i] pivot 时仅需要 i 即可继续判断下一个元素。这与本文第六节代码的指针移动规则一一对应。三向切分把数组一次性切成小于 / 等于 / 大于三个区等于区直接跳过不参与递归从而大大减小递归时的区间大小这正是它在大量重复元素场景下优于普通快排的原因。2. 荷兰国旗问题三向切分的经典马甲同样的思想可以直接搬到 荷兰国旗.md 中的经典问题给定一个整数数组给定一个值 K该值在原数组中一定存在要求把数组中小于 K 的元素放到数组的左边大于 K 的元素放到数组的右边等于 K 的元素放到数组的中间最终返回等于 K 部分的左右两个下标值。这本质上就是三向切分而 LeetCode 75 颜色分类用 0、1、2 分别表示红、白、蓝原地排序则是它最直接的变体——把 1 当作 pivot所有 0 放左边、2 放右边。荷兰国旗问题在 leetcode 上的题目就是 leetcode75 颜色分类。把这几篇对照阅读可以清楚地看到一个算法内核多种题目外衣的脉络。3. 快速排序的复杂度与稳定性既然最终用的还是快速排序框架其复杂度特性也一并继承详见 快速排序.md时间复杂度最好情况每次分区都恰好把数组分成大小接近相等的两半递归树平衡时间复杂度为O(nlogn)最坏情况如数组正序或逆序递归调用约 n-1 次退化为O(n²)空间复杂度主要来自递归造成的栈空间最好情况为O(logn)对应递归树深度最坏情况为O(n)稳定性快速排序的关键字比较和交换是跳跃进行的例如两个相等的 1 在一次分区后可能互换前后相对位置因此是不稳定排序。4. 进一步优化三数取中 插入排序阈值针对正序/逆序数组退化为 O(n²)以及小数组递归开销大这两个痛点快速排序.md 还给出了两个与三向切分可叠加的优化手段三数取中法选取low、mid、high三个位置元素的中位数放到nums[low]作为基准值避免选到最大值或最小值当基准mid low ((high-low) 1)配合三次条件交换即可实现和插入排序搭配使用插入排序在元素个数较少时效率最高因此设定阈值如 7当high - low 7时改用插入排序大于阈值时才走快速排序递归。仓库最终给出的组合方案是三数取中 三向切分 插入排序的完整 Java/Python 实现感兴趣的读者可以直接在 快速排序.md 中查看完整代码。八、举一反三如何改编为最大数回到本文开头提到的 LeetCode 179 最大数。两题的差别只有一个字最小 / 最大。因此改编也非常直接翻转比较规则求最大数时当mn nm时定义 m 大于 n即排在前面把第六节代码中compareTo的比较方向反过来即可或者等价地先按最小数的规则排序再把结果逆序拼接注意前导零边界LeetCode 179 的题目本身要求若拼接得到的最大数开头是 0例如输入全为 0 的数组[0, 0]结果应返回0而不是00这是实现时需要单独处理的边界情况证明部分完全复用前文的规则有效性 反证法证明只依赖比较规则本身的良定义性方向取反后论证过程对称成立。九、小结与延伸阅读回顾全篇这道题的完整思维链是拼数问题输出为大数 → 先转字符串全排列不可行 → 转化为排序问题自定义拼接序比较规则mnvsnm用自反性、对称性、传递性证明规则有效用反证法相邻 / 非相邻两种情况证明排序结果即最小拼接数用三向切分快速排序实现 O(nlogn) 级别的求解。在 algorithm-base 仓库中本文内容位于 合成.md并在 README.md 的排序算法秒杀题目章节中被收录。建议按以下顺序延伸阅读把这条排序算法秒杀题目的主线串起来快速排序.md三向切分、三数取中、插入排序阈值等全部优化手段的完整推导与代码荷兰国旗.md三向切分的经典问题表述与 LeetCode 75 颜色分类双解法leetcode75颜色分类.md颜色分类在数组篇中的独立题解逆序对问题.md 与 翻转对.md同样依托排序框架归并排序解决的另两类高频面试题。赞分享文档教程知识库【免费下载链接】algorithm-base一位酷爱做饭的程序员立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址https://gitcode.com/gh_mirrors/al/algorithm-base点击查看免费下载相关推荐如何使用 ipatool 在 Windows/Linux/macOS 上搜索并下载 iOS 应用包如何使用 ipatool 在 Windows/Linux/macOS 上搜索并下载 iOS 应用包 你手头有个 App Store 应用想拿到它的 IPA 文CLI开发工具剑指 Offer 45用自定义排序规则把数组排成最小的数 —— LeetCode-Book 三语言题解详解剑指 Offer 45用自定义排序规则把数组排成最小的数 —— LeetCode Book 三语言题解详解 本篇以 LeetCode Book 仓库中《剑指示例工程LeetCode-Go 题解 179. Largest Number拼接比较排序法求解最大数LeetCode Go 题解 179. Largest Number拼接比较排序法求解最大数 本篇以 LeetCode Go 仓库中 179. Largest示例工程上一篇NHSE动物森友会存档编辑器完全指南 - 打造你的梦想岛屿下一篇ComfyUI启动失败5个终极技巧让你告别依赖地狱 创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考