ஒரு வரிசை லீட்கோட் தீர்வின் தரவரிசை மாற்றம்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான் பேஸ்புக் கூகிள்
அணி

ஒரு வரிசை லீட்கோட் தீர்வின் தரவரிசை மாற்றம் எங்களுக்கு ஒரு வரிசை முழு எண்களின். வரிசை அல்லது கொடுக்கப்பட்ட வரிசை வரிசைப்படுத்தப்படவில்லை. கொடுக்கப்பட்ட வரிசையில் ஒவ்வொரு முழு எண்க்கும் நாம் அணிகளை ஒதுக்க வேண்டும். அணிகளை ஒதுக்க சில கட்டுப்பாடுகள் உள்ளன.

  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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (NlogN), ஆர்டர் செய்யப்பட்ட வரைபடத்தைப் பயன்படுத்தியதால், செருக, நீக்குதல் மற்றும் தேடலுக்கான மடக்கைக் காரணி எங்களிடம் உள்ளது.

விண்வெளி சிக்கலானது

ஓ (என்), ஏனெனில் உள்ளீட்டில் உள்ள கூறுகளை சேமிக்க ஆர்டர் செய்யப்பட்ட வரைபடத்தைப் பயன்படுத்துகிறோம்.