Nisbi dərəcələr Leetcode Solution

Çətinlik səviyyəsi Asan
Tez-tez soruşulur google
alqoritmlər kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions çeşidləyiciBaxılıb 30

Problem nisbi rütbələr Leetcode Solution nisbi rütbələri təmsil edən bir vektor və ya bir sıra sətir qaytarmağımızı istər. Biz ilə təmin olunur array idmançıların əldə etdikləri xalı əks etdirir. Sonra rütbələri təyin etmək üçün verilmiş bal massivindən istifadə edirik. İlk 3 namizəd üçün kiçik bir dəyişiklik var. Bunun əvəzinə onlara 1, 2 və ya 3 nömrələrini vermək, Qızıl, Gümüş və Bürünc medallar təyin etməliyik. İlk 3 namizəddən başqa, onlara 4-dən n-ə qədər sadə rəqəmlər təyin edə bilərik. Bir neçə nümunəyə nəzər salaq.

Nisbi dərəcələr Leetcode SolutionPin

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

İzahat: Verilən sıra idmançıların qazandıqları balları təmsil etdiyi üçün. Ən yüksək bal toplayan idmançıya Qızıl medal və s. Veriləcək. Beləliklə idmançıya 3, Qızıl medal 2, İdmançıya 1, Gümüş medal XNUMX, İdmançıya isə Bürünc medal verdik.

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

İzahat: Ən yaxşı 3 namizəd medallarla təltif olunduğundan, qalan namizədlərə dərəcə verilir. Beləliklə, ilk 3 namizədi medal təyin etdik və müvafiq namizədlərə 4 və 5 dərəcələrini təyin etdik.

Yanaşma

Problemli nisbi rütbələr Leetcode Solution, medalları ilk 3 namizədə təyin etməyimizi və qalan namizədlərə dərəcələr təyin etməyimizi tələb edir. Düşünə biləcəyi ən sadə şey verilən ardıcıllığı sıralamaqdır. Ancaq sıraları orijinal indekslərə təyin etməliyik. Beləliklə, verilən ardıcıllığı birbaşa düzəltsək, orijinal indeksləri əldən verəcəyik. Rütbələrin təyin edilməsinə qərar verə bilməyəcək. Beləliklə, orijinal indeksləri itirməməyimiz üçün orijinal indeksləri ballarla birlikdə saxlayan yeni bir vektor və ya bir sıra yaradırıq. Bu yeni massivi və ya vektoru sıralayırıq. Çeşidlədikdən sonra yalnız Qızıl, Gümüş və Bürünc medalları müvafiq namizədlərə və 4-dən n-ə qədər olan layiq namizədlərə təyin edirik. Bunu edə bilərik, çünki yeni dəyişdirilmiş massivimizi və ya vektorumuzu çeşidlədikdə, orijinal indekslər də saxlanılan dəyərlərə uyğun mövqelərini dəyişdirirlər.

Nisbi Rütbələr üçün Leetcode Həlli Kodu

Nisbi Rütbələr Leetcode Solution üçün C ++ kodu

#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 kodu Nisbi Rütbələr Leetcode Solution

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (NlogN), çünki çeşidləmə O (NlogN) vaxtını tələb edir, burada N - vektorun və ya massivin ionlaşdırılan elementlərinin sayı.

Kosmik Mürəkkəblik

O (NlogN), çünki O (NlogN) yer tutan çeşidləmə istifadə etdik. Məkan mürəkkəbliyi də zaman mürəkkəbliyi ilə eynidir.

Şərh yaz

Translate »
1