2 optimal 6ms~9ms java solutions beating 99%


  • 0
    public class Solution {
    //6~8ms solution
    public String[] findRelativeRanks_noSorting(int[] nums) {            
         int min = nums[0], max = min;
         for(int i = 1;i < nums.length; i++){
               if(nums[i]<min) min = nums[i];
               else if(nums[i]>max) max = nums[i];
         }
         int[] index = new int[max-min+1];
         for(int i = 0; i < nums.length; i++) index[nums[i]-min]=i+1;
         String[] result = new String[nums.length];
         int order = 1;
         for(int i = index.length-1; i > -1; i--){
            if(index[i]==0)continue;
            else if(order>3) result[index[i]-1] = String.valueOf(order);
            else if(order>2) result[index[i]-1] = "Bronze Medal";
            else if(order>1) result[index[i]-1] = "Silver Medal";
            else result[index[i]-1] = "Gold Medal"; 
            order++;
    }
    return result;
    }
    //8~10ms solution
    public String[] findRelativeRanks_Sorting(int[] nums) {
        int[] Hash = new int[nums.length];
    for(int i = 0; i<nums.length;i++) Hash[i]=i; //O(n)  space(O(n))
    //Arrays.sort(Hash,(i,j)->(nums[i]-nums[j])); requires Hash to be Integer[] rather than int[], it's very costly.
    QuickSort(Hash,0,Hash.length-1,nums); //O(nlogn), which is the same as Arrays.sort(Hash,(i,j)->(nums[i]-nums[j])), but Hash can be primitive array
    String[] result = new String[nums.length]; 
    if(nums.length>=3){
        result[Hash[0]]="Gold Medal";result[Hash[1]]="Silver Medal";result[Hash[2]]="Bronze Medal";
        for(int i = 3; i<result.length;i++) result[Hash[i]]=String.valueOf(i+1);  //O(n)
    }
    else if(nums.length>=2){
        result[Hash[0]]="Gold Medal";result[Hash[1]]="Silver Medal";
    }
    else result[Hash[0]]="Gold Medal";
    return result;
    }
    public static void QuickSort(int[] array,int left,int right, int[] function){
    //sort is done when the left index is bigger than the right index
    if(left>=right) return;
    int pivot = partition(array,left,right,function);
    //int pivot = partitionReverse(array,left,right);
    QuickSort(array,left,pivot-1,function);
    QuickSort(array,pivot+1,right,function);
    }
    public static int partition(int[] array,int left,int right,int[] function){
    //here we pick array[left] as pivot,and compare array[j] with it
    int pivotindex = left;
    //index moving from left to right
    int l = left+1;
    //index moving from right to left
    int r = right;
    while(true){
    	while(l<=r&&function[l]>=function[pivotindex])
    		l++;
    	while(l<=r&&function[r]<=function[pivotindex])
    		r--;
    	if(l<r){
    		swap(array,l,r,function);l++;r--;
    	}
    	else break;
    }
    //"r" is not equal to the pivot index that we want
    //so we swap array[pivotindex] with array[r]
    swap(array,pivotindex,r,function);
    //and return right as pivot index
    return r;
    }
    public static void swap(int[] array, int firstIndex, int secondIndex, int[] function) {
    int temp = array[firstIndex];
    array[firstIndex] = array[secondIndex];
    array[secondIndex] = temp;
    temp = function[firstIndex];
    function[firstIndex] = function[secondIndex];
    function[secondIndex] = temp;
    }
    }

Log in to reply
 

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