剑指Offer8:将数组排列成最大数
1.题目描述
给定一组非负整数,重新排列它们的顺序使之组成一个最大的整数。
示例 1:
输入: [10,2]
输出: 210
示例?2:
输入: [3,30,34,5,9]
输出: 9534330
说明: 输出结果可能非常大,所以你需要返回一个字符串而不是整数。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/largest-number
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2.解析
可以仿照冒泡排序,比较两个数组合后的大小,将大的放在前边
【比较可以使用compareTo(),也可以使用Integer.valueOf()先转为数字在比较,但以为可能组合后的数会超过int的最大值,所以使用Long.valueOf()】
如:[10,2]
"10+2"=="102"
"2+10"=="210"
"210">"102"
所以调整数组为[2,10]
3.代码
import java.util.Scanner;
/**
* @author zhaomin
* @date 2020/7/28 9:46
*/
public class Solution {
public static String largestNumber(int[] nums) {
if(nums==null||nums.length==0){
return new String();
}
for(int i=0;i<nums.length-1;i++){
boolean flag=false;
String res="";
for(int j=0;j<nums.length-1-i;j++){
String s1=res+nums[j]+nums[j+1];//进行数字组合
String s2=res+nums[j+1]+nums[j];
if(s1.compareTo(s2)<0){//进行比较,并交换
int tem=nums[j];
nums[j]=nums[j+1];
nums[j+1]=tem;
flag=true;
}
}
if(!flag){
break;
}
}
StringBuilder sb=new StringBuilder();
for(int num:nums){
sb.append(num);
}
if(sb.charAt(0)==‘0‘) return "0";
return sb.toString();
}
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
String str=scanner.nextLine();
String[] arr=str.split(",");
int[] nums=new int[arr.length];
for(int i=0;i<nums.length;i++){
nums[i]=Integer.valueOf((arr[i]));
}
System.out.println(largestNumber(nums));
}
}
剑指Offer8:将数组排列成最大数
原文地址:https://blog.51cto.com/14234228/2513970