అర్రే లీట్‌కోడ్ సొల్యూషన్ యొక్క ర్యాంక్ ట్రాన్స్ఫార్మ్


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అమెజాన్ <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> గూగుల్
అర్రే

అర్రే లీట్‌కోడ్ సొల్యూషన్ యొక్క ర్యాంక్ ట్రాన్స్‌ఫార్మ్ సమస్య మాకు అందించింది అమరిక పూర్ణాంకాల. శ్రేణి లేదా ఇచ్చిన క్రమం క్రమబద్ధీకరించబడలేదు. ఇచ్చిన క్రమంలో ప్రతి పూర్ణాంకానికి ర్యాంకులను కేటాయించాలి. ర్యాంకులను కేటాయించడానికి కొన్ని పరిమితులు ఉన్నాయి.

  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), మేము ఆర్డర్‌ చేసిన మ్యాప్‌ను ఉపయోగించినందున, చొప్పించడం, తొలగించడం మరియు శోధించడం కోసం లాగరిథమిక్ కారకం ఉంది.

అంతరిక్ష సంక్లిష్టత

పై), ఎందుకంటే మేము ఇన్‌పుట్‌లోని అంశాలను నిల్వ చేయడానికి ఆర్డర్ చేసిన మ్యాప్‌ను ఉపయోగిస్తాము.