Accept Java Solution O(nlogn) Mergesort


  • 0
    J

    Actually, this question is relative easy to get the solution. It just a sort problem, therefore, we can come up with some classical sort methods, like merge sort. Of course, the following code has some place can be optimized, but it is not the biggest problem here.

    public static boolean compare(String s1, String s2) {
    	String s1s2 = s1 + s2;
    	String s2s1 = s2 + s1;
    	if (s1.length() < s2.length()) {
    		if (s1s2.compareTo(s2s1)>0)
    			return false;
    		else
    			return true;
    	} else {
    		if (s1s2.compareTo(s2s1)<0)
    			return true;
    		else
    			return false;
    	}
    }
    
    public static void mergeSort(int[] array) {
    	if (array.length > 1) {
    		int[] left = leftHalf(array);
    		int[] right = rightHalf(array);
    		mergeSort(left);
    		mergeSort(right);
    		merge(array, left, right);
    	}
    }
    
    public static int[] leftHalf(int[] array) {
    	int size1 = array.length / 2;
    	int[] left = new int[size1];
    	for (int i = 0; i < size1; i++) {
    		left[i] = array[i];
    	}
    	return left;
    }
    
    public static int[] rightHalf(int[] array) {
    	int size1 = array.length / 2;
    	int size2 = array.length - size1;
    	int[] right = new int[size2];
    	for (int i = 0; i < size2; i++) {
    		right[i] = array[i + size1];
    	}
    	return right;
    }
    
    public static void merge(int[] result, int[] left, int[] right) {
    	int i1 = 0;
    	int i2 = 0;
    	for (int i = 0; i < result.length; i++) {
    		if (i2 >= right.length
    				|| (i1 < left.length && !compare(left[i1] + "", right[i2]
    						+ ""))) {
    			result[i] = left[i1];
    			i1++;
    		} else {
    			result[i] = right[i2];
    			i2++;
    		}
    	}
    }
    
    public static String largestNumber(int[] num) {
    	mergeSort(num);
    	StringBuilder result = new StringBuilder();
    	for (int i = 0; i < num.length; i++) {
    		result.append(num[i]);
    		if (num[i] == 0 && i == 0)
    			break;
    	}
    	return result.toString();
    }

Log in to reply
 

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