एर्रे लेटकोड समाधानको रैंक रूपान्तरण


कठिनाई तह सजिलो
बारम्बार सोधिन्छ अमेजन फेसबुक गुगल
एरे

एरे लेटकोड समाधानको समस्या रैank्क रूपान्तरणले हामीलाई एक प्रदान गर्यो array पूर्णांकको। एर्रे वा दिईएको अनुक्रम क्रमबद्ध छैन। हामीले क्रममा प्रत्येक पूर्णांकमा श्रेणीहरू तोक्न आवश्यक छ। त्यहाँ केहि प्रतिबन्धहरु छन् रेन्कहरु निर्दिष्ट गर्न को लागी।

  1. श्रेणीहरू १ को साथ सुरु हुनुपर्छ।
  2. ठूलो संख्या, उच्च रैंक (संख्यात्मक रूपमा ठूलो)।
  3. श्रेणीहरू प्रत्येक पूर्णांकको लागि सकेसम्म सानो हुनुपर्दछ।

एर्रे लेटकोड समाधानको रैंक रूपान्तरण

त्यसो भए, हामी केहि उदाहरणहरूमा एक नजर राख्दछौं।

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

स्पष्टीकरण: यदि हामी दिईएको इनपुट क्रमबद्ध गर्छौं भने उदाहरण बुझ्न सजिलो हुनेछ। क्रमबद्ध पछि, इनपुट [१०, २०, ,०, ]०] हुन्छ। अब यदि हामी दिईएको नियमहरु पालना गर्छौं भने। नयाँ संशोधित एर्रे अनुसार [१, २,,,]] श्रेणीहरू हुनेछन्। यदि हामी आउटपुटमा एलिमेन्टहरू मेल खान्छौं भने। तिनीहरू समान छन्, आउटपुटको शुद्धता पुष्टि गर्दै।

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

स्पष्टीकरण: किनकि इनपुटमा सबै तत्वहरू समान छन्। यसैले सबै सँग समान रैक हुनै पर्छ १। त्यसैले आउटपुटमा १ को तीन उदाहरणहरू हुन्छन्।

एर्रे लेटकोड समाधानको रैंक रूपान्तरणको लागि दृष्टिकोण

एरे लेटकोड समाधानको समस्या रैank्क रूपान्तरणले हामीलाई दिइएको अनुक्रममा स्तरहरू तोक्न भन्यो। पूरा गर्नुपर्ने शर्तहरू समस्या वर्णनमा पहिले नै भनिएको छ। त्यसोभए, तिनीहरूलाई एक पटक फेरि वर्णन गर्नुको सट्टा। हामी सीधा समाधानको माध्यमबाट जान्छौं। उदाहरणको रूपमा देखाईएको छ। क्रमबद्ध अनुक्रममा स्तरहरू तोक्न यो सजिलो छ। त्यसो भए, हामी दिईएको इनपुट अनुक्रममा एलिमेन्टहरू भण्डारण गर्न अर्डर गरिएको नक्शा प्रयोग गर्छौं। एक अर्डर गरिएको नक्शाको प्रयोगले निश्चित गर्दछ कि तत्वहरू क्रमबद्ध गरिएको छ।

अब हामीले तेस्रो सर्तसँग व्यवहार गर्नुपर्नेछ। तेस्रो सर्तले भन्छ कि हामीले सकेसम्म सब भन्दा साना र .्कहरू तोक्नु पर्छ। त्यसो भए, हामी केवल नक्सामा उपस्थित कुञ्जीहरू १ बाट नम्बरहरू नियुक्त गर्दछौं। यसले सबै तीन लगाइएको शर्तहरूको ख्याल राख्छ। ठूलो संख्या को श्रेणी उच्च छ। श्रेणीहरू १ बाट सुरू हुन्छ। तिनीहरू सकेसम्म सानो छन्।

अब, हामी केवल इनपुट अनुक्रमको माध्यमबाट पार गर्छौं र नक्सामा भण्डार गरिएका रैंकहरू निर्दिष्ट गर्दछौं।

कोड

C ++ कोड एरे लीटकोड समाधानको रैंक ट्रान्सफॉर्मको लागि

#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), किनकि हामी एक अर्डर गरिएको नक्शा प्रयोग गर्‍यौं, हामीसँग सम्मिलन, मेटाउन, र खोजीको लागि लोगारिदमिक कारक छ।

ठाउँ जटिलता

O (N), किनभने हामी एक अर्डर गरिएको नक्शा को उपयोग इनपुट मा तत्वहरू भण्डारण गर्न प्रयोग गर्दछौं।