Share My java solution using merge-sort


  • 0
    X
    public class Solution {
        public String largestNumber(int[] num) {
            int length=num.length;
    		merge_sort(num,0,length-1);
    		
    		StringBuffer result=new StringBuffer();
    		for(int n:num){
    		    if(result.toString().equals("")&&n==0) continue;
    			result.append(n);
    		}
    		
    		if(result.toString().equals("")) return Integer.toString(0);
    		return result.toString();
        }
        
        public void merge_sort(int[] a,int start,int end){
    		int mid;
    		if(start<end){
    			mid=(start+end)/2;
    			merge_sort(a,start,mid);
    			merge_sort(a,mid+1,end);
    			merge(a,start,mid,end);
    		}
    	}
    	
    	public void merge(int[] a,int start,int mid, int end){
    		int n1=mid-start+1;
    		int n2=end-mid;
    		
    		int[] front=new int[n1];
    		int[] back=new int[n2];
    		
    		for(int i=0;i<n1;i++){
    			front[i]=a[start+i];
    		}
    		for(int i=0;i<n2;i++){
    			back[i]=a[mid+i+1];
    		}
    		
    		int i=0,j=0,k=start;
    		while(i<n1&&j<n2){
    			if(compare(Integer.toString(front[i]),Integer.toString(back[j]))){
    				a[k++]=front[i++];
    			}
    			else{
    				a[k++]=back[j++];
    			}
    		}
    		while(i<n1){
    			a[k++]=front[i++];
    		}
    		while(j<n2){
    			a[k++]=back[j++];
    		}
    	}
    	
    	public boolean compare(String s1,String s2){//if true, s1 should be ahead of s2
    		int l1=s1.length();
    		int l2=s2.length();
    		int i=0;
    		for(i=0;i<l1&&i<l2;i++){
    			int i1= Integer.parseInt(String.valueOf(s1.charAt(i)));
    			int i2=Integer.parseInt(String.valueOf(s2.charAt(i)));
    			if(i1==i2) continue;
    			if(i1<i2) return false;
    			if(i1>i2) return true;
    		} 
    		//now i==l1
    		if(l1<l2){//s2 is longer 
    			String news2= s2.substring(i, l2);
    			return compare(s1,news2);
    		}
    		//now i==l2
    		else if(l1>l2){//s1 is longer 
    			String news1= s1.substring(i, l1);
    			return compare(news1,s2);
    		}
    		//now i==l1==l2
    		else
    			return false;
    	}
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.