379.Reorder array to construct the minimum number-将数组重新排序以构造最小值（中等题）

本文主要是介绍379.Reorder array to construct the minimum number-将数组重新排序以构造最小值（中等题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

将数组重新排序以构造最小值

1. 题目

   给定一个整数数组，请将其重新排序，以构造最小值。

2. 样例

   给定 [3, 32, 321]，通过将数组重新排序，可构造 6 个可能性数字：
   3+32+321=332321
   3+321+32=332132
   32+3+321=323321
   32+321+3=323213
   321+3+32=321332
   321+32+3=321323
   其中，最小值为 321323，所以，将数组重新排序后，该数组变为 [321, 32, 3]。

3. 挑战

   在原数组上完成，不使用额外空间。

4. 题解

   本题类似于184.Largest Number-最大数（中等题），是求最小数。但是由于题目要求不能使用额外空间，则需要我们自己实现排序算法（这里使用的是快排算法），元素大小比较可参见184题。

public class Solution {/*** @param nums n non-negative integer array* @return a string*/public String minNumber(int[] nums) {StringBuilder sb = new StringBuilder();quickSort(nums,0,nums.length-1);for (int i=0;i<nums.length;i++){if (sb.length() == 0 && nums[i] == 0){continue;}sb.append(String.valueOf(nums[i]));}return sb.length() == 0 ? "0" : sb.toString();}private int compare(int o1, int o2){return (String.valueOf(o1)+String.valueOf(o2)).compareTo(String.valueOf(o2)+String.valueOf(o1));}private void quickSort(int[] a, int left, int right){if (left < right){int temp = a[left];int i = left;int j = right;while (i < j){while (j > i && compare(a[j],temp) >=0){j--;}while (i < j && compare(a[i],temp) <= 0){i++;}if (i < j){swap(a, i, j);}}swap(a, left, j);quickSort(a,left,i-1);quickSort(a, i+1, right);}}private void swap(int[] a, int i, int j){int temp = a[j];a[j] = a[i];a[i] = temp;}
}

Last Update 2016.11.11

这篇关于379.Reorder array to construct the minimum number-将数组重新排序以构造最小值（中等题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---