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

• ``````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;
}
}``````

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