首页 > 代码库 > 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