# Simple Sorting O(n log n) solution

• ``````class Solution {
public:
vector<string> findRelativeRanks(vector<int>& nums) {
vector<int> rank;
for(int i=0; i<nums.size(); ++i) rank.push_back(i);

sort(rank.begin(), rank.end(), [&](int a, int b){return nums[a] > nums[b];});
vector<string> ranks(nums.size());

for(int i=3; i<nums.size(); ++i){
ranks[rank[i]] = std::to_string(i+1);
}

if(nums.size() > 0) ranks[rank[0]] = "Gold Medal";
if(nums.size() > 1) ranks[rank[1]] = "Silver Medal";
if(nums.size() > 2) ranks[rank[2]] = "Bronze Medal";

return ranks;
}
};``````

• @kevin36 can you explain

[&](int a, int b){return nums[a] > nums[b];}

sort() can take a function as parameter, but how exactly this statement is working here?

• @rajnish952
`[&](int a, int b){return nums[a] > nums[b];}` is a c++ lambda function, the syntactic is kinda strange that they use `[]` instead of making `lambda` a keyword, which is just a names less function which is passed to the sort function.

I hope this clears this up for you

• I got motivated and write a Java solution, it takes 8~9ms and beats 99%

``````    public class Solution {
public String[] findRelativeRanks(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;
}
}``````

• @kevin36 thanks :)

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