剑指offer-32、把数组排成最⼩的数
<h2 id="题描述">题⽬描述</h2><p>输⼊⼀个正整数数组，把数组⾥所有数字拼接起来排成⼀个数，打印能拼接出的所有数字中最⼩的⼀个。例如输⼊数组 {3，32，321} ，则打印出这三个数字能排成的最⼩数字为 321323 。</p>
<p>示例1<br>
输⼊：<br>
返回值："321323"</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="自定义排序推荐解法">自定义排序（推荐解法）</h3>
<p>这道题要求拼起来的数是最⼩的数字，其实是⼀个排序问题，只要理解了这⼀点，就可以快速解决。</p>
<p>假设有两个字符串 s1=3 ， s2=32 ，那 s1+s2=332 , s2+s1=323 ,也就是 s1+s2>s2+s1 。</p>
<p>像上⾯这种情况，要想拼接起来的数最⼩，肯定是 s2 在前⾯， s1 在后⾯。</p>
<p>⽽在数组中，我们要使所有的拼接起来是最⼩，则需要两两⽐较，类似排序，把满⾜ s1+s2>s2+s1 的s1 放到后⾯， s2 放到前⾯。</p>
<pre><code class="language-java">public class Solution {
public String PrintMinNumber(int [] numbers) {
String[] strs = new String;
for(int i = 0; i < numbers.length; i++)
strs = String.valueOf(numbers);
Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
StringBuilder res = new StringBuilder();
for(String s : strs)
res.append(s);
return res.toString();
}
}
</code></pre>
<ul>
<li>时间复杂度 : O(nlogn) , n 为 nums 数组的⻓度，使⽤内置排序函数的平均时间复杂度为O(nlogn) ，最差为 O(n2 ) 。</li>
<li>空间复杂度: O(N)</li>
</ul>
<h3 id="手动实现快速排序">手动实现快速排序</h3>
<p>我们也可以不依赖内部排序，自己手动实现</p>
<pre><code class="language-java">public class Solution {
public String PrintMinNumber(int[] numbers) {
if (numbers == null || numbers.length == 0) return "";
String[] strs = new String;
for (int i = 0; i < numbers.length; i++) {
strs = String.valueOf(numbers);
}
// 手动实现快速排序
quickSort(strs, 0, strs.length - 1);
StringBuilder sb = new StringBuilder();
for (String s : strs) {
sb.append(s);
}
return sb.toString();
}
private void quickSort(String[] strs, int left, int right) {
if (left >= right) return;
int pivotIndex = partition(strs, left, right);
quickSort(strs, left, pivotIndex - 1);
quickSort(strs, pivotIndex + 1, right);
}
private int partition(String[] strs, int left, int right) {
String pivotValue = strs;
int i = left;
for (int j = left; j < right; j++) {
// 使用自定义比较规则
if ((strs + pivotValue).compareTo(pivotValue + strs) <= 0) {
swap(strs, i, j);
i++;
}
}
swap(strs, i, right);
return i;
}
private void swap(String[] strs, int i, int j) {
String temp = strs;
strs = strs;
strs = temp;
}
}
</code></pre>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19102970
頁:
[1]