首页 > 代码库 > Java-Largest Number
Java-Largest Number
Given a list of non negative integers, arrange them such that they form the largest number.
For example, given [3, 30, 34, 5, 9]
, the largest formed number is 9534330
.
Note: The result may be very large, so you need to return a string instead of an integer.
Credits:
Special thanks to @ts for adding this problem and creating all test cases.
给一个乱序数组 要求将其依次排列其能组成的最大数
基本要求还是排序 只是比较大小的依据不同 比如412<41但415>41比较的依据是谁放在后面组成的数更大 所以 只要将n1和n2都转换为String 分别前后放置 比较这两个组成String的大小 返回结果 排序方法采用的是快速排序 一开始在sort()函数部分 进行递归时 i错写为mid导致 死循环 花费了好长时间才发现 代码如下:
public class Solution { public static String largestNumber(int[] num) { String ss=""; if(num.length==0){ return ss; } sort(num, 0, num.length-1); if(num[num.length-1]==0)return "0"; for(int i=num.length-1;i>=0;i--){ ss+=String.valueOf(num[i]); } return ss; } public static void sort(int[] num,int left,int right){ if(right-left<10){ for(int i=left;i<right;i++){ for(int j=i;j<=right;j++){ if(bigger(num[i], num[j])==1){ int tmp=num[j]; num[j]=num[i]; num[i]=tmp; } } } }else{ int mid=mid(num, left, right); int i=left; int j=right-1; for(;;){ while(bigger(num[++i],mid)==-1){}; while(bigger(num[--j],mid)==1){}; if(i<j){ swap(num, i, j); }else{ break; } } swap(num, i, right-1); sort(num, left, i-1); sort(num, i+1,right); } } public static int mid(int[] num,int left,int right){ int mid=(left+right)/2; if(bigger(num[left],num[mid])==1){ swap(num, left, mid); } if(bigger(num[mid],num[right])==1){ swap(num, right, mid); } if(bigger(num[left],num[mid])==1){ swap(num, left, mid); } swap(num, mid, right-1); return num[right-1]; } public static void swap(int[] num,int i,int j){ int tmp=num[j]; num[j]=num[i]; num[i]=tmp; } public static int bigger(int num1,int num2){ String ss1=String.valueOf(num1)+String.valueOf(num2);; String ss2=String.valueOf(num2)+String.valueOf(num1); for(int i=0;i<ss1.length();i++){ if(ss1.charAt(i)>ss2.charAt(i)){ return 1; }else{ if(ss1.charAt(i)<ss2.charAt(i)){ return -1; } } } return 0; }}
Java-Largest Number
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。