Հարաբերական կարգերի 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, մինչև վաստակավոր թեկնածուները: Մենք կարող ենք դա անել, քանի որ, երբ տեսակավորում ենք մեր նոր ձևափոխված զանգվածը կամ վեկտորը, բնօրինակ ինդեքսները փոխում են նաև իրենց դիրքերը `համապատասխան պահված արժեքներին:

Հարաբերական դասակների կոդերի լուծման կոդ

C ++ կոդ ՝ Relative Ranks Leetcode Solution- ի համար

#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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (NlogN), քանի որ տեսակավորման համար պահանջվում է O (NlogN) ժամանակ, որտեղ N –ն է ՝ դասավորված վեկտորը կամ զանգվածը իոնների տարրերի քանակը:

Տիեզերական բարդություն

O (NlogN), քանի որ մենք օգտագործել ենք տեսակավորում, որը տանում է O (NlogN) տարածք: Տիեզերական բարդությունը նույնպես նույնն է, ինչ ժամանակի բարդությունը: