Массив Leetcode чечиминин ранг трансформациясы


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

Массивдин рейтинги трансформациясы Leetcode Solution бизге жардам берди согуштук тизме бүтүн сандар. Массив же берилген ырааттуулук иргелбейт. Берилген ырааттуулуктагы ар бир бүтүн санга рангдарды беришибиз керек. Катарларды ыйгаруу үчүн айрым чектөөлөр бар.

  1. Катар 1ден башталышы керек.
  2. Сан канчалык чоң болсо, ранг ошончолук жогору болот (сандык мааниде чоңураак).
  3. Ар бир бүтүн сан үчүн мүмкүн болушунча кичинекей болушу керек.

Массив Leetcode чечиминин ранг трансформациясы

Ошентип, бир нече мисалдарды карап көрөлү.

arr = [40,10,20,30]
[4,1,2,3]

Түшүндүрмө: Берилген маалыматты иреттесек, мисалды түшүнүү оңой болот. Сорттоодон кийин, киргизүү болуп калат [10, 20, 30, 40]. Эми берилген эрежелерди сактасак. Жаңы модификацияланган массивге ылайык, катарлар [1, 2, 3, 4] болот. Эгерде биз чыгарылыштагы элементтерге дал келсек. Алар бирдей, чыгарылган нерсенин тууралыгын тастыкташат.

[100,100,100]
[1, 1, 1]

Түшүндүрүү: Киргизилген элементтердин бардыгы бирдей болгондуктан. Ошентип, бардыгы бирдей рангга ээ болушу керек, демек, натыйжада 1дин үч мисалы камтылган.

Массив Leetcode чечиминин ранг трансформациясы ыкмасы

Массивдин рейтинги трансформациясы Leetcode Solution чечими бизден берилген ырааттуулукка рангдарды берүүнү суранды. Аткарыла турган шарттар көйгөй баяндоосунда баяндалган. Ошентип, аларды дагы бир жолу сүрөттөөнүн ордуна. Биз түздөн-түз чечим аркылуу өтөт. Ошентип, мисалда көрүнүп тургандай. Даражаларды иреттелген ырааттуулукка бөлүштүрүү оңой. Ошентип, элементтерди берилген киргизүү ырааттуулугунда сактоо үчүн буйрутма картаны колдонобуз. Буйрутмаланган картаны колдонуу элементтердин иреттелгендигин текшерет.

Эми үчүнчү шарт менен күрөшүшүбүз керек. Үчүнчү шартта мүмкүн болушунча эң кичине рангдарды ыйгаруу керектиги айтылат. Ошентип, биз картада көрсөтүлгөн баскычтарга 1ден сандарды гана ыйгарабыз. Бул коюлган үч шарттын бардыгына кам көрөт. Чоңураак сандардын даражасы жогору. Катар 1ден башталат. Алар мүмкүн болушунча аз.

Эми, биз жөн гана киргизүү ырааттуулугун басып өтүп, картада сакталган рангдарды ыйгарабыз.

коду

Массив Leetcode чечиминин ранг трансформациясы үчүн C ++ коду

#include <bits/stdc++.h>
using namespace std;

vector<int> arrayRankTransform(vector<int>& arr) {
    map<int, int> m;
    for(auto x: arr)
        m[x] = 1;
    int lst = 0;
    for(auto x: m){
        m[x.first] = lst + 1;
        lst++;
    }
    for(int i=0;i<arr.size();i++)
        arr[i] = m[arr[i]];
    return arr;
}

int main(){
    vector<int> input = {40, 10, 30, 20};
    vector<int> output = arrayRankTransform(input);
    for(auto x: input)
        cout<<x<<" ";
}
4 1 3 2

Array Leetcode Solution чечиминин Java коду

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static int[] arrayRankTransform(int[] arr) {
        Map<Integer, Integer> m = new TreeMap<Integer, Integer>();
        for(int x: arr)
            m.put(x, 1);
        int lst = 0;
        for(Integer x: m.keySet()){
            m.put(x, lst + m.get(x));
            lst = m.get(x);
        }
        for(int i=0;i<arr.length;i++)
            arr[i] = m.get(arr[i]);
        return arr;
    }
    
  public static void main (String[] args) throws java.lang.Exception
  {
    int[] input = {40, 10, 30, 20};
    int[] output = arrayRankTransform(input);
    for(int x: output)
      System.out.print(x+" ");
  }
}
4 1 3 2

Комплекстик анализ

Убакыт татаалдыгы

O (NlogN), биз буйрутмаланган картаны колдонгондуктан, киргизүү, жок кылуу жана издөө үчүн логарифмдик фактор бар.

Космостун татаалдыгы

O (N), анткени биз элементтерди киргизүү үчүн буйрутмаланган картаны колдонобуз.