Решение Leetcode за относителни класи


Ниво на трудност Лесно
Често задавани в Google
сортиране

Проблемът Relative Ranks Leetcode Solution ни изисква да върнем вектор или масив от низове, представляващи относителните рангове. Ние сме снабдени с масив което представлява резултатът, получен от спортисти. След това използваме дадения масив от оценки, за да присвоим ранговете. Има малка промяна за първите 3 кандидати. Вместо да им присвояваме прости числа 1, 2 или 3. Трябва да присвоим златен, сребърен и бронзов медал. Освен топ 3 кандидата, можем да им присвоим прости числа от 4 до n. Нека да разгледаме няколко примера.

Решение Leetcode за относителни класи

[1, 2, 3]
["Bronze Medal", "Silver Medal", "Gold Medal"]

Обяснение: Тъй като даденият масив представлява резултатите, постигнати от спортистите. Състезателят с най-висок резултат ще получи златен медал и т.н. По този начин дадохме златен медал на спортиста с резултат 3, сребърен медал на спортиста с резултат 2 и бронзов медал на спортиста с резултат 1.

[5, 4, 3, 2, 1]
["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]

Обяснение: Тъй като на първите 3 кандидати се присъждат медали, а на останалите кандидати се присъжда ранг. По този начин ние сме присвоили медали на 3-те най-добри кандидати и сме дали ранг 4 и 5 на съответните кандидати.

Подход

Проблемът Relative Ranks Leetcode Solution ни изисква да присвоим медалите на 3-те най-добри кандидати и да дадем ранга на останалите кандидати. Най-простото нещо, за което човек може да се сети, е да сортира дадената последователност. Но трябва да присвоим ранговете на първоначалните индекси. Така че, ако директно сортираме дадената последователност, тогава ще пропуснем оригиналните индекси. И няма да може да реши да присвоява званията. По този начин, за да сме сигурни, че няма да загубим оригиналните индекси, ние създаваме нов вектор или масив, който съхранява оригиналните индекси с резултатите. Ние сортираме този нов масив или вектор. След сортирането ние просто присвояваме златен, сребърен и бронзов медал на съответните кандидати и класира от 4 до n, на заслужилите кандидати. Можем да направим това, защото когато сортираме новия си модифициран масив или вектор, оригиналните индекси също разменят своите позиции, съответстващи на запазените стойности.

Код за относително класиране Leetcode решение

C ++ код за решение на Leetcode за относителни рангове

#include <bits/stdc++.h>
using namespace std;

vector<string> findRelativeRanks(vector<int>& nums) {
    vector<pair<int,int>> temp;
    int n = nums.size();
    for(int i=0;i<n;i++){
        temp.push_back(make_pair(nums[i], i));
    }
    sort(temp.rbegin(), temp.rend());
    vector<string> answer(n);
    answer[temp[0].second] = "Gold Medal";
    if(n>=2){
        answer[temp[1].second] = "Silver Medal";
    }
    if(n>=3){
        answer[temp[2].second] = "Bronze Medal";
    }
    for(int i=3;i<n;i++)
        answer[temp[i].second] = to_string(i+1);
    return answer;
}

int main(){
    vector<int> nums = {5, 4, 3, 2, 1};
    vector<string> answer = findRelativeRanks(nums);
    for(auto x: answer)cout<<x<<" ";
}
Gold Medal Silver Medal Bronze Medal 4 5

Java код Относителни класирания Leetcode Решение

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
  
    public static String[] findRelativeRanks(int[] nums) {
        int n = nums.length;
        int[][] pair = new int[nums.length][2];
        for (int i = 0; i < n; i++) {
            pair[i][0] = nums[i];
            pair[i][1] = i;
        }
        
        Arrays.sort(pair, (a, b) -> (b[0] - a[0]));
        
        String[] result = new String[nums.length];
        result[pair[0][1]] = "Gold Medal";
        if(n>=2)
            result[pair[1][1]] = "Silver Medal";
        if(n>=3)
            result[pair[2][1]] = "Bronze Medal";
        for (int i = 3; i < nums.length; i++) {
            result[pair[i][1]] = Integer.toString(i+1);
        }

        return result;
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    int[] nums = {5, 4, 3, 2, 1};
    String[] answer = findRelativeRanks(nums);
    for(int i=0;i<5;i++)
      System.out.print(answer[i] + " ");
  }
}
Gold Medal Silver Medal Bronze Medal 4 5

Анализ на сложността

Сложност във времето

O (NlogN), тъй като сортирането изисква O (NlogN) време, където N е броят на елементите йон, който векторът или масивът се сортират.

Сложност на пространството

O (NlogN), тъй като сме използвали сортирането, което отнема O (NlogN) пространство. Сложността на пространството също е същата като сложността във времето.