සාපේක්ෂ ශ්‍රේණි ලීට්කෝඩ් විසඳුම


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ගූගල්
වර්ග කිරීම

සාපේක්ෂ ශ්‍රේණි ලීට්කෝඩ් විසඳුම අපෙන් ඉල්ලා සිටින්නේ දෛශිකයක් හෝ සාපේක්ෂ ශ්‍රේණි නියෝජනය කරන නූල් සමූහයක් ආපසු ලබා දෙන ලෙසයි. අපට ලබා දී ඇත්තේ අ අරාව එය ක්‍රීඩක ක්‍රීඩිකාවන් ලබාගත් ලකුණු නියෝජනය කරයි. එවිට අපි ලබා දී ඇති ලකුණු අරාව භාවිතා කරමින් ශ්‍රේණිගත කිරීම පවරමු. ඉහළම අපේක්ෂකයින් 3 දෙනා සඳහා කුඩා වෙනසක් ඇත. 1, 2, හෝ 3 යන සරල අංක ඔවුන්ට ලබා දීම වෙනුවට අපට රන්, රිදී සහ ලෝකඩ පදක්කම් ලබා දිය යුතුය. ඉහළම අපේක්ෂකයින් 3 දෙනා හැරුණු විට, අපට ඔවුන්ට 4 සිට n දක්වා සරල අංක ලබා දිය හැකිය. උදාහරණ කිහිපයක් දෙස බලමු.

සාපේක්ෂ ශ්‍රේණි ලීට්කෝඩ් විසඳුම

[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 දෙනා අදාළ අපේක්ෂකයින්ට ලබා දී ඇත.

ප්රවේශය

සාපේක්ෂ ශ්‍රේණිගත කිරීමේ ලීට්කෝඩ් විසඳුම අපෙන් ඉල්ලා සිටින්නේ ඉහළම අපේක්ෂකයින් තිදෙනාට පදක්කම් ලබා දෙන ලෙසත් අනෙක් අපේක්ෂකයින් සඳහා ශ්‍රේණිගත කිරීම් ලබා දෙන ලෙසත් ය. කෙනෙකුට සිතිය හැකි සරලම දෙය නම් දී ඇති අනුක්‍රමය වර්ග කිරීමයි. නමුත් අපි මුල් දර්ශක වලට ශ්‍රේණිගත කිරීම කළ යුතුයි. එබැවින්, අපි ලබා දී ඇති අනුක්‍රමය කෙලින්ම වර්ග කළහොත්, අපට මුල් දර්ශක මග හැරෙනු ඇත. තවද, නිලයන් පැවරීමට තීරණය කිරීමට නොහැකි වනු ඇත. මේ අනුව අපට මුල් දර්ශක නැති නොවන බවට වග බලා ගැනීම සඳහා, අපි නව දෛශිකයක් හෝ අරාවක් නිර්මාණය කර මුල් දර්ශක ලකුණු සමඟ ගබඩා කරමු. අපි මෙම නව අරාව හෝ දෛශිකය වර්ග කරමු. වර්ග කිරීමෙන් පසුව, අපි රන්, රිදී සහ ලෝකඩ පදක්කම අදාළ අපේක්ෂකයින්ට සහ 3 සිට n දක්වා ශ්‍රේණිගත කිරීම සුදුසුකම් ලත් අපේක්ෂකයින්ට පවරමු. අපට මෙය කළ හැක්කේ අපගේ නව වෙනස් කරන ලද අරාව හෝ දෛශිකය වර්ග කරන විට, මුල් දර්ශක ද ගබඩා කර ඇති අගයන්ට අනුරූපව ඒවායේ ස්ථාන මාරු කරන බැවිනි.

සාපේක්ෂ ශ්‍රේණි ලීට්කෝඩ් විසඳුම සඳහා කේතය

සාපේක්ෂ ශ්‍රේණි ලීට්කෝඩ් විසඳුම සඳහා සී ++ කේතය

#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

ජාවා කේතය සාපේක්ෂ ශ්‍රේණි ලීට්කෝඩ් විසඳුම

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) අවකාශය ගත කරන වර්ග කිරීම භාවිතා කර ඇති බැවින්. අවකාශයේ සංකීර්ණතාව ද කාල සංකීර්ණතාවයට සමාන වේ.