QuickSort in java, beating 94%


  • 0
    L
    public class Solution {
    public String largestNumber(int[] nums) {
        int N = nums.length;
        String[] strs = new String[N];
        for(int i = 0; i< N; i++){
            strs[i] = String.valueOf(nums[i]);
        }
        
        quicksort(strs, 0, N-1);
        
        if(strs[0].equals("0")) return "0";
        StringBuilder sb = new StringBuilder();
        for(String s: strs) sb.append(s);
        return sb.toString();
    }
    private void quicksort(String[] a, int lo, int hi){
        if(lo>=hi) return;
        int lt = lo, gt = hi;
        int i = lo+1;
        String v = a[lo];
        while(i<=gt){
            String s = a[i];
            if(compare(s,v) > 0) exch(a, i++, lt++);
            else if(compare(s, v) < 0) exch(a, i, gt--);
            else i++;
        }
        quicksort(a, lo, lt-1);
        quicksort(a, gt+1, hi);
    }
    private int compare(String i, String j){
        String str1 = i+j;
        String str2 = j+i;
        return str1.compareTo(str2);
    }
    private void exch(String[] a, int i, int j){
        String tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    

    }


  • -1
    L

    Alternatively, Java API method Arrays.sort(String[], Comparator<String>) uses quicksort implicitly.

    public class Solution {
    public String largestNumber(int[] nums) {
        int N = nums.length;
        String[] strs = new String[N];
        for(int i = 0; i< N; i++){
            strs[i] = String.valueOf(nums[i]);
        }
        
        Arrays.sort(strs, new Comparator<String>(){
            public int compare(String i, String j){
                String str1 = i + j;
                String str2 = j + i;
                return str2.compareTo(str1);
            }
            });
        
        if(strs[0].equals("0")) return "0";
        StringBuilder sb = new StringBuilder();
        for(String s: strs) sb.append(s);
        return sb.toString();
    }
    

    }


Log in to reply
 

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