Simple Sorting O(n log n) solution


  • 17
    K
    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;
        }
    };

  • 2
    R

    @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?


  • 2
    K

    @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


  • 0

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

  • 0
    R

    @kevin36 thanks :)


Log in to reply
 

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