Λύση σχετικού βαθμού 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 έως ν, στους άξιους υποψηφίους. Μπορούμε να το κάνουμε αυτό γιατί όταν ταξινομούμε τον νέο τροποποιημένο πίνακα ή φορέα, οι αρχικοί δείκτες αλλάζουν επίσης τις θέσεις τους που αντιστοιχούν στις αποθηκευμένες τιμές.

Κωδικός για σχετικές τάξεις Λύση κωδικού 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 Relative Ranks 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

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας

O (NlogN), επειδή η ταξινόμηση απαιτεί χρόνο O (NlogN), όπου N είναι ο αριθμός των στοιχείων που ταξινομούνται στο διάνυσμα ή στον πίνακα.

Διαστημική πολυπλοκότητα

O (NlogN), αφού έχουμε χρησιμοποιήσει ταξινόμηση που παίρνει χώρο O (NlogN). Η πολυπλοκότητα του διαστήματος είναι επίσης η ίδια με την πολυπλοκότητα του χρόνου.