अ‍ॅरे लीटकोड सोल्यूशनचे रँक ट्रान्सफॉर्म


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन फेसबुक Google
अरे

अ‍ॅरे लीटकोड सोल्यूशनच्या रँक ट्रान्सफॉर्मने आम्हाला एक प्रदान केले अॅरे पूर्णांक अ‍ॅरे किंवा दिलेला क्रम क्रमबद्ध नाही. दिलेल्या क्रमातील प्रत्येक पूर्णांकासाठी आपल्याला क्रमांक निश्चित करणे आवश्यक आहे. गुण निश्चित करण्यासाठी काही निर्बंध आहेत.

  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 म्हणून आउटपुटमध्ये XNUMX ची तीन उदाहरणे आहेत.

अ‍ॅरे लीटकोड सोल्यूशनच्या रँक ट्रान्सफॉर्मसाठी दृष्टीकोन

अ‍ॅरे लीटकोड सोल्यूशनच्या रँक ट्रान्सफॉर्मच्या समस्येने आम्हाला दिलेल्या अनुक्रमे क्रमांक निश्चित करण्यास सांगितले. पूर्ण करण्याच्या अटी आधीपासूनच समस्या वर्णनात नमूद केल्या आहेत. तर त्याऐवजी पुन्हा एकदा त्यांचे वर्णन करण्याऐवजी. आम्ही थेट निराकरण करू. म्हणून, उदाहरणात पाहिल्याप्रमाणे. क्रमवारी लावून क्रमवारी लावणे अधिक सुलभ आहे. तर आम्ही दिलेल्या इनपुट क्रमात घटक संचयित करण्यासाठी ऑर्डर केलेला नकाशा वापरतो. ऑर्डर केलेला नकाशा वापरणे हे सुनिश्चित करते की घटकांची क्रमवारी लावली आहे.

आता आपण तिसर्‍या अटला सामोरे जायला हवे. तिसरी अट सांगते की आम्ही शक्य तितक्या लहान रँक निश्चित करणे आवश्यक आहे. तर, आम्ही नकाशात असलेल्या की पासून फक्त 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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एनएलजीएन), आम्ही ऑर्डर केलेला नकाशा वापरल्यामुळे आमच्याकडे अंतर्भूत करणे, हटविणे आणि शोध यासाठी लॉगॅरिथमिक घटक आहे.

स्पेस कॉम्प्लेक्सिटी

ओ (एन), कारण आम्ही इनपुटमध्ये घटक साठवण्यासाठी ऑर्डर केलेला नकाशा वापरतो.