Bir sıra Leetcode həllinin dərəcə çevrilməsi

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon Facebook google
alqoritmlər Geyim kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 30

Bir Array Leetcode Çözümünün Sıra Çevrilməsinin problemi bizə bir array tam ədədi. Massiv və ya verilən ardıcıllıq çeşidlənməyib. Verilən ardıcıllıqla hər bir ədədə dərəcələr təyin etməliyik. Rütbələrin verilməsi üçün bəzi məhdudiyyətlər mövcuddur.

  1. Sıralar 1 ilə başlamalıdır.
  2. Sayı nə qədər böyükdürsə, dərəcə o qədər yüksəkdir (ədədi baxımdan daha böyükdür).
  3. Sıralamalar hər bir tam say üçün mümkün qədər kiçik olmalıdır.

Bir sıra Leetcode həllinin dərəcə çevrilməsiPin

Beləliklə, bir neçə nümunəyə nəzər salaq.

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

İzahat: Verilən girişləri sıralasaq nümunəni anlamaq daha asan olacaq. Çeşidlədikdən sonra giriş [10, 20, 30, 40] olur. İndi verilən qaydalara əməl etsək. Sıralar, yeni dəyişdirilmiş massivə görə [1, 2, 3, 4] olacaqdır. Çıxışdakı elementlərə uyğun gəlsək. Çıxışın düzgünlüyünü təsdiqləyən eynidirlər.

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

İzahat: Girişdəki bütün elementlər eyni olduğundan. Beləliklə, hamısı 1-in eyni dərəcəsinə sahib olmalıdır. Beləliklə, çıxış 1-in üç nümunəsini ehtiva edir.

Bir sıra Leetcode həllinin dərəcə çevrilməsinə yanaşma

Bir Array Leetcode Çözümünün Sıra Transformasiyası problemi, verilən ardıcıllığa dərəcələr təyin etməyimizi istədi. Görülməli olan şərtlər problemin təsvirində artıq qeyd edilmişdir. Beləliklə, onları bir daha izah etmək əvəzinə. Həll yolu ilə birbaşa gedəcəyik. Nümunədə göründüyü kimi. Sıralanmış ardıcıllığa dərəcələr təyin etmək daha asandır. Beləliklə, elementləri verilmiş giriş ardıcıllığında saxlamaq üçün sifariş edilmiş bir xəritədən istifadə edirik. Sifarişli xəritədən istifadə etmək elementlərin sıralanmış qaydada olmasını təmin edir.

İndi üçüncü şərtlə məşğul olmalıyıq. Üçüncü şərt, mümkün qədər ən kiçik dərəcələri təyin etməliyik. Beləliklə, sadəcə xəritədə mövcud olan düymələrə 1-dən rəqəmlər veririk. Bu, qoyulmuş üç şərtin hamısına cavab verir. Daha böyük rəqəmlərin dərəcəsi daha yüksəkdir. Sıra 1-dən başlayır. Mümkün qədər azdır.

İndi sadəcə giriş ardıcıllığından keçirik və xəritədə saxlanılan dərəcələri təyin edirik.

Kodu

Bir Array Leetcode Solution Sıra Transformasiyası üçün C ++ kodu

#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

Bir Array Leetcode Çözümünün Java kodu Rank Transform

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (NlogN), sifarişli bir xəritədən istifadə etdiyimiz üçün daxil etmə, silmə və axtarış üçün loqaritmik faktora sahibik.

Kosmik Mürəkkəblik

O (N), elementləri girişdə saxlamaq üçün sifariş edilmiş bir xəritədən istifadə etdiyimiz üçün.

Şərh yaz

Translate »
1