એરે લીટકોડ સોલ્યુશનનું રેન્ક ટ્રાન્સફોર્મ


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એમેઝોન ફેસબુક Google
અરે

એરે લીટકોડ સોલ્યુશનના સમસ્યા રેન્ક ટ્રાન્સફોર્મે અમને પ્રદાન કર્યું છે એરે પૂર્ણાંકોની. એરે અથવા આપેલ ક્રમ છૂટા થયેલ છે. આપેલ અનુક્રમમાં દરેક પૂર્ણાંકને રેન્ક આપવાની જરૂર છે. રેન્કને સોંપવા માટે કેટલાક નિયંત્રણો છે.

  1. રેન્ક 1 સાથે પ્રારંભ થવો આવશ્યક છે.
  2. મોટી સંખ્યા, ઉચ્ચ ક્રમ (આંકડાકીય દ્રષ્ટિએ મોટો).
  3. દરેક પૂર્ણાંક માટે રેન્ક શક્ય તેટલા નાના હોવા જોઈએ.

એરે લીટકોડ સોલ્યુશનનું રેન્ક ટ્રાન્સફોર્મ

તેથી, ચાલો થોડા ઉદાહરણો જોઈએ.

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

સમજૂતી: જો આપેલ ઇનપુટને સ sortર્ટ કરીએ તો ઉદાહરણ સમજવું વધુ સરળ રહેશે. સ sortર્ટ કર્યા પછી, ઇનપુટ [10, 20, 30, 40] બને છે. હવે જો આપેલ નિયમોનું પાલન કરીએ. નવા સુધારેલા એરે મુજબ રેન્ક [1, 2, 3, 4] રહેશે. જો આપણે આઉટપુટના તત્વો સાથે મેચ કરીએ. તેઓ સમાન છે, આઉટપુટની ચોકસાઈની પુષ્ટિ.

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

સમજૂતી: ઇનપુટના બધા તત્વો સમાન છે. આમ બધામાં સમાન ક્રમ હોવો આવશ્યક છે. 1. તેથી આઉટપુટમાં 1 ના ત્રણ ઉદાહરણો છે.

એરે લીટકોડ સોલ્યુશનના રેન્ક ટ્રાન્સફોર્મ માટે અભિગમ

એરે લીટકોડ સોલ્યુશનના સમસ્યા રેન્ક ટ્રાન્સફોર્મે અમને આપેલા ક્રમ પર રેન્ક સોંપવાનું કહ્યું. શરતો કે જે મળવાની છે તે સમસ્યાના વર્ણનમાં પહેલેથી જ જણાવેલ છે. તેથી, ફરીથી તેનું વર્ણન કરવાને બદલે. અમે સીધા જ સોલ્યુશનમાંથી પસાર થઈશું. તેથી, ઉદાહરણ તરીકે જોયું. ક્રમાંકિત ક્રમમાં ક્રમ સોંપી દેવાનું વધુ સરળ છે. તેથી, આપેલ ઇનપુટ અનુક્રમમાં તત્વો સંગ્રહવા માટે અમે orderedર્ડર કરેલા નકશાનો ઉપયોગ કરીએ છીએ. ઓર્ડર કરેલા નકશાનો ઉપયોગ એ સુનિશ્ચિત કરે છે કે તત્વો સortedર્ટ ક્રમમાં છે.

હવે, આપણે ત્રીજી શરતનો સામનો કરવો જોઇએ. ત્રીજી શરત જણાવે છે કે આપણે શક્ય તેટલું નાનો ક્રમ સોંપવો જ જોઇએ. તેથી, અમે નકશા પર હાજર કીઓ માટે ફક્ત 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

જાવા કોડ રેન્ક ટ્રાન્સફોર્મ anફ એરે લીટકોડ સોલ્યુશન

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), અમે ઓર્ડર કરેલા નકશાનો ઉપયોગ કર્યો હોવાથી, શામેલ કરવા, કાtionી નાખવા અને શોધવા માટે લarગરીધમિક પરિબળ છે.

અવકાશ જટિલતા

ઓ (એન), કારણ કે ઇનપુટમાં તત્વો સંગ્રહવા માટે અમે orderedર્ડર કરેલા નકશાનો ઉપયોગ કરીએ છીએ.