剑指 Offer 45. 把数组排成最小的数
输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2]输出: "102"
示例 2:
输入: [3,30,34,5,9]输出: "3033459"
提示:
0 < nums.length <= 100
说明:
输出结果可能非常大,所以你需要返回一个字符串而不是整数
拼接起来的数字可能会有前导 0,最后结果不需要去掉前导 0
做题思路:
其实做这道题,建议先看一下左神的快排代码,了解一下快排代码的套路。
package basic_class_01;import java.util.Arrays;public class Code_04_QuickSort { public static void quickSort(int[] arr) { if (arr == null || arr.length < 2) { return; } quickSort(arr, 0, arr.length - 1); } public static void quickSort(int[] arr, int l, int r) { if (l < r) { swap(arr, l + (int) (Math.random() * (r - l + 1)), r); int[] p = partition(arr, l, r); quickSort(arr, l, p[0] - 1); quickSort(arr, p[1] + 1, r); } } public static int[] partition(int[] arr, int l, int r) { int less = l - 1; int more = r; while (l < more) { if (arr[l] < arr[r]) { swap(arr, ++less, l++); } else if (arr[l] > arr[r]) { swap(arr, --more, l); } else { l++; } } swap(arr, more, r); return new int[] { less + 1, more }; } public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } }
然后把快排的思路学习到了,以后再来仔细看这道题的做题思路。
比如,【30,3】,“30”+“3”=“303” <“3” + “30” =330这个可以看出30应该排在3后面。
可以得出它的排序规则如下:
若拼接的字符串x+y>y+x,则x大于y,即x在y的前面
反之,x+y<y+x,则x小于y,即x在y的后面
x小于y代表:排序完成后,x在y左边;否则反之。
图片源自@jyd
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 res = new StringBuilder(); for (String s : strs) res.append(s); return res.toString(); } public void quickSort(String[] strs, int low, int high) { if (low < high) { int middle = getMiddle(strs, low, high); quickSort(strs, low, middle - 1); quickSort(strs, middle + 1, high); } } public int getMiddle(String[] strs, int low, int high) { //数组的第一个数为基准元素 String temp = strs[low]; while (low < high) { //从后向前找比基准小的数 while (low < high && (strs[high] + temp).compareTo(temp + strs[high]) >= 0) high--; //把比基准小的数移到低端 strs[low] = strs[high]; //从前向后找比基准大的数 while (low < high && (strs[low] + temp).compareTo(temp + strs[low]) <= 0) low++; //把比基准大的数移到高端 strs[high] = strs[low]; } strs[low] = temp; return low; } }
这位(logiLong - 力扣(LeetCode) (leetcode-cn.com))力友根据快排思路写的代码如下,可以与左神的快排代码相对照:
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]); } sort(strs, 0, strs.length - 1); StringBuilder ans = new StringBuilder(); for(String s : strs) ans.append(s); return ans.toString(); } // 下面是快排的代码 private void sort(String[] arr, int start, int end){ if(start >= end) return; int pivot = partition(arr, start, end); sort(arr, start, pivot - 1); sort(arr, pivot + 1, end); } private int partition(String[] arr, int start, int end){ int pivot = end; // 默认选取最后一个作为基准 int i = start; for(int j = start; j < end; j++){ if((arr[j] + arr[pivot]).compareTo(arr[pivot] + arr[j]) < 0) { if(i != j) swap(arr, i, j); i++; } } swap(arr, i, pivot); return i; } private void swap(String[] arr, int index1, int index2){ String temp = arr[index1]; arr[index1] = arr[index2]; arr[index2] = temp; } }
这是K神的代码,可以在面试的时候快速的写出。
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 res = new StringBuilder(); for(String s : strs) res.append(s); return res.toString(); } void quickSort(String[] strs, int l, int r) { if(l >= r) return; int i = l, j = r; String tmp = strs[i]; 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++; tmp = strs[i]; strs[i] = strs[j]; strs[j] = tmp; } strs[i] = strs[l]; strs[l] = tmp; quickSort(strs, l, i - 1); quickSort(strs, i + 1, r); } }
当然也可以采用内置函数的方式,代码如下:
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(); } }
参考链接:
https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/solution/offer45ba-shu-zu-pai-cheng-zui-xiao-de-s-eh8d/
https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/solution/mian-shi-ti-45-ba-shu-zu-pai-cheng-zui-xiao-de-s-4/ 2
__EOF__
本文作者:Rains
本文链接:https://www.cnblogs.com/RainsX/p/15302490.html