每日一题 - 剑指 Offer 45. 把数组排成最小的数

题目信息

时间： 2019-07-01

题目链接：Leetcode

tag： 快速排序

难易程度：中等

题目描述：

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

示例1:

输入: [10,2] 输出: "102"

示例2:

输入: [3,30,34,5,9] 输出: "3033459"

提示

1. 0 < nums.length <= 100

解题思路

本题难点

此题求拼接起来的 “最小数字” ，本质上是一个排序问题。

具体思路

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

代码

class Solution { public String minNumber(int[] nums) { String[] strs = new String[nums.length]; //初始化： 字符串列表 strs ，保存各数字的字符串格式； for(int i = 0; i < nums.length; i++){ strs[i] = String.valueOf(nums[i]); } //列表排序： 应用以上 “排序判断规则” ，对 strs 执行排序； quickSort(strs,0,strs.length - 1); //返回值： 拼接 strs 中的所有字符串，并返回。 StringBuilder res = new StringBuilder(); for(String s : strs){ res.append(s); } return res.toString(); } public void quickSort(String[] strs,int l,int r){ if(l >= r){ return; } int i = l; int j = r; while(i < j){ //若 右边+左边组合字符串大于 左边+右边组合字符串参数，则右边指针向左移 while((strs[j] + strs[l]).compareTo(strs[l] + strs[j]) >= 0 && i < j){ j--; } //若 左边+右边组合字符串大于 右边+左边组合字符串参数，则左边指针向左移 while((strs[i] + strs[l]).compareTo(strs[l] + strs[i]) <= 0 && i < j){ i++; } //两字符串交换位置 swap(strs,i,j); } //将第一个字符串交换到最终位置，左边字符串小于，右边字符串大于 swap(strs,l,i); //递归排序左边字符串数组 quickSort(strs,l,j-1); //递归排序右边字符串数组 quickSort(strs,j+1,r); } public void swap(String[] strs,int i ,int j){ String temp = strs[i]; strs[i] = strs[j]; strs[j] = temp; } }

复杂度分析：

时间复杂度 O(NlogN) ：N 为最终返回值的字符数量（ strs 列表的长度 ≤N ）；使用快排或内置函数的平均时间复杂度为 O(NlogN) ，最差为 O(N ^2 ) 。空间复杂度 O(N) ： 字符串列表 strs占用线性大小的额外空间。

其他优秀解答

解题思路

Java 内置数组排序函数： (x, y) -> (x + y).compareTo(y + x)

代码

class Solution { public String minNumber(int[] nums) { String[] strs = new String[nums.length]; for(int i = 0; i < nums.length; i++) strs[i] = String.valueOf(nums[i]); Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x)); StringBuilder res = new StringBuilder(); for(String s : strs) res.append(s); return res.toString(); } }