剑指 Offer 45. 把数组排成最小的数
本问题对应的 leetcode 原文链接：剑指 Offer 45. 把数组排成最小的数
对应打卡问题：【排序算法运用】剑指 Offer 45. 把数组排成最小的数
问题描述
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2]
输出: "102"
示例 2：
输入: [3,30,34,5,9]
输出: "3033459"
提示:
0 < nums.length <= 100
说明:
- 输出结果可能非常大，所以你需要返回一个字符串而不是整数
- 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0
解题思路
视频讲解直达： 本题视频讲解
代码实现
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]);
}
quickSort(strs, 0, strs.length - 1);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < strs.length; i++) {
sb.append(strs[i]);
}
return sb.toString();
}
///时间nlogn，空间 On
// 快速排序模版（和普通快速排序模版一样的，除了比较那里不一样）
private void quickSort(String[] arr, int left, int right) {
if (left > right) {
return;
}
int i = partition(arr, left, right);
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}
int partition(String[] arr, int left, int right){
String pivot = arr[left]; // 中间值
int i = left;
int j = right;
while (i < j) {
while (i <= j && (arr[i] + pivot).compareTo(pivot + arr[i]) <= 0) {
i++;
}
while (i <= j && (arr[j] + pivot).compareTo(pivot + arr[j]) >= 0) {
j--;
}
if(i >= j){
break;
}
String temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
arr[left] = arr[j];
arr[j] = pivot;
return j;
}
}
时间复杂度：O(nlogn)
额外空间复杂度：O(n)