අරා ලීට්කෝඩ් විසඳුමක ශ්‍රේණිගත පරිවර්තනය


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇමේසන් ෆේස්බුක් ගූගල්
අරා

අරා ලීට්කෝඩ් විසඳුමක ශ්‍රේණිගත පරිවර්තනය අපට ලබා දී ඇත්තේ අ අරාව නිඛිලවල. අරාව හෝ දී ඇති අනුක්‍රමය වර්ග කර නොමැත. දී ඇති අනුපිළිවෙලෙහි එක් එක් නිඛිලයට අපි ශ්‍රේණි පැවරිය යුතුය. නිලයන් පැවරීම සඳහා යම් සීමාවන් තිබේ.

  1. ශ්‍රේණි 1 න් ආරම්භ විය යුතුය.
  2. සංඛ්‍යාව විශාල වන තරමට ඉහළ තරාතිරම (සංඛ්‍යාත්මකව විශාල වේ).
  3. එක් එක් නිඛිලය සඳහා ශ්‍රේණි හැකි තරම් කුඩා විය යුතුය.

අරා ලීට්කෝඩ් විසඳුමක ශ්‍රේණිගත පරිවර්තනය

ඉතින්, අපි උදාහරණ කිහිපයක් දෙස බලමු.

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

පැහැදිලි කිරීම: අපි දී ඇති ආදානය වර්ග කළහොත් උදාහරණය තේරුම් ගැනීම පහසු වනු ඇත. වර්ග කිරීමෙන් පසුව, ආදානය [10, 20, 30, 40] බවට පත්වේ. දැන් අපි දී ඇති නීති අනුගමනය කරන්නේ නම්. නව වෙනස් කරන ලද අරාව අනුව ශ්‍රේණි [1, 2, 3, 4] වනු ඇත. අපි ප්‍රතිදානයේ මූලද්‍රව්‍ය සමඟ ගැලපෙන්නේ නම්. ඒවා සමාන වේ, ප්‍රතිදානයේ නිරවද්‍යතාවය සනාථ කරයි.

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

පැහැදිලි කිරීම: ආදානයේ සියලුම අංග එක හා සමාන බැවින්. මේ අනුව සියල්ලන්ටම 1 වන ශ්‍රේණියක් තිබිය යුතුය. එබැවින් ප්‍රතිදානයේ අවස්ථා 1 ක් අඩංගු වේ.

අරා ලීට්කෝඩ් විසඳුමක ශ්‍රේණිගත පරිවර්තනය සඳහා ප්‍රවේශය

අරාව ලීට්කෝඩ් විසඳුමක ශ්‍රේණිගත පරිවර්තනය පිළිබඳ ගැටළුව අප විසින් ලබා දී ඇති අනුක්‍රමයට ශ්‍රේණිගත කිරීම් ලබා දෙන ලෙස ඉල්ලා සිටියේය. සපුරාලිය යුතු කොන්දේසි ගැටළු විස්තරයේ දැනටමත් සඳහන් කර ඇත. එබැවින් ඒවා නැවත වරක් විස්තර කරනවා වෙනුවට. අපි කෙලින්ම විසඳුම හරහා යමු. ඉතින්, උදාහරණයේ පෙනෙන පරිදි. වර්ග කළ අනුපිළිවෙලකට ශ්‍රේණිගත කිරීම පහසුය. එබැවින්, දී ඇති ආදාන අනුපිළිවෙලෙහි මූලද්‍රව්‍ය ගබඩා කිරීම සඳහා අපි ඇණවුම් කළ සිතියමක් භාවිතා කරමු. ඇණවුම් කළ සිතියමක් භාවිතා කිරීමෙන් මූලද්‍රව්‍ය පිළිවෙලට ඇති බව සහතික කරයි.

දැන් අපි තුන්වන කොන්දේසිය සමඟ කටයුතු කළ යුතුයි. තෙවන කොන්දේසියෙහි සඳහන් වන්නේ අප හැකි තරම් කුඩාම නිලයන් පැවරිය යුතු බවයි. එබැවින්, අපි සිතියමේ ඇති යතුරු සඳහා 1 සිට අංක ලබා දෙමු. මෙය පැනවූ කොන්දේසි තුනම බලා ගනී. විශාල සංඛ්යා වල තරාතිරම වැඩි ය. ශ්‍රේණි 1 සිට ආරම්භ වේ. ඒවා හැකි තරම් කුඩා ය.

දැන්, අපි හුදෙක් ආදාන අනුක්‍රමය හරහා ගමන් කර සිතියමෙහි ගබඩා කර ඇති ශ්‍රේණි පවරන්නෙමු.

කේතය

අරා ලීට්කෝඩ් විසඳුමක ශ්‍රේණිගත පරිවර්තනය සඳහා සී ++ කේතය

#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

ජාවා කේතය ශ්‍රේණියේ අරා ලීට්කෝඩ් විසඳුමක පරිවර්තනය

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), අපි ඇණවුම් කළ සිතියමක් භාවිතා කළ බැවින් ඇතුළත් කිරීම, මකා දැමීම සහ සෙවීම සඳහා ල ar ු ගණක සාධකය අප සතුව ඇත.

අභ්‍යවකාශ සංකීර්ණතාව

මත), ආදානයේ මූලද්‍රව්‍ය ගබඩා කිරීම සඳහා අපි ඇණවුම් කළ සිතියමක් භාවිතා කරන බැවිනි.