本文主要是介绍379.Reorder array to construct the minimum number-将数组重新排序以构造最小值(中等题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
将数组重新排序以构造最小值
题目
给定一个整数数组,请将其重新排序,以构造最小值。
样例
给定 [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]。挑战
在原数组上完成,不使用额外空间。
题解
本题类似于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-将数组重新排序以构造最小值(中等题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!