Салыштырмалуу рангдар Leetcode Solution


Кыйынчылык деңгээли жеңил
Көп суралган Гугл
сорттоо

Leatcode Solution колдонулган салыштырмалуу рангдар көйгөйү векторду же салыштырмалуу катарларды чагылдырган бир катар саптарды кайтарып берүүнү өтүнөт. Биз менен камсыз кылынат согуштук тизме бул спортчулар алган упайды билдирет. Андан кийин рангдарды ыйгаруу үчүн берилген упай массивин колдонобуз. Алдыңкы 3 талапкерге бир аз өзгөрүү болду. Алардын ордуна жөнөкөй сандарды 1, 2 же 3 берсек, биз Алтын, Күмүш жана Коло медалдарын ыйгарышыбыз керек. Эң алдыңкы 3 талапкерден тышкары, биз аларга 4төн nге чейин жөнөкөй сандарды бере алабыз. Бир нече мисалдарды карап көрөлү.

Салыштырмалуу рангдар Leetcode Solution

[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-орундарды тиешелүү талапкерлерге ыйгардык.

жакындоо

Leatcode Solution Relative Ranks көйгөйү бизден алдыңкы 3 талапкерге медалдарды ыйгарууну жана калган талапкерлерге даражаларды ыйгарууну суранат. Эң жөнөкөй нерсе - берилген ырааттуулукту иреттөө. Бирок биз баштапкы индекстерге катарларды ыйгарышыбыз керек. Ошентип, эгерде биз берилген ырааттуулукту түздөн-түз иргеп алсак, анда баштапкы индекстерди өткөрүп жиберебиз. Жана наамдарды ыйгарууну чече албай калат. Ошентип, баштапкы индекстерди жоготпошубуз үчүн, баштапкы индекстерди упайлары менен кошо сактай турган жаңы вектор же массив түзөбүз. Бул жаңы массивди же векторду иреттейбиз. Сорттоп бүткөндөн кийин, Алтын, Күмүш жана Коло медалын тиешелүү талапкерлерге ыйгарып, 4төн nге чейин, татыктуу талапкерлерге тапшырабыз. Биз муну жасай алабыз, анткени биз жаңы модификацияланган массивди же векторду иреттегенде, баштапкы индекстер өзүлөрүнүн позицияларын сакталган маанилерге ылайыкташтырышат.

Салыштырмалуу рангдар коду Leetcode Solution

Салыштырмалуу рангдар Leetcode Solution үчүн C ++ коду

#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 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) мейкиндигин ээлеген сорттоону колдондук. Космостун татаалдыгы дагы убакыттын татаалдыгы менен бирдей.