കുറച്ച ഫോമിലേക്ക് ഒരു ശ്രേണി പരിവർത്തനം ചെയ്യുക


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ലിങ്ക്ഡ് Snapchat സോം യാഹൂ
അറേ ഹാഷ് ക്രമപ്പെടുത്തൽ

പ്രശ്നം പ്രസ്താവന

“ഒരു അറേ കുറച്ച ഫോമിലേക്ക് പരിവർത്തനം ചെയ്യുക” എന്ന പ്രശ്നം, വലുപ്പം n വ്യത്യസ്ത ഘടകങ്ങളുടെ പൂർണ്ണസംഖ്യകളുടെ ഒരു നിര നിങ്ങൾക്ക് നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു. 0 മുതൽ n-1 വരെയുള്ള ശ്രേണിയിൽ‌ പുതിയ സംഖ്യകൾ‌ അറേയിൽ‌ സ്ഥാപിക്കുന്ന തരത്തിൽ‌ അറേ കുറയ്‌ക്കാൻ‌ പ്രശ്‌ന പ്രസ്താവന ആവശ്യപ്പെട്ടു. അറേയുടെ ഏറ്റവും ചെറിയ സംഖ്യ 0 ആയി കണക്കാക്കണം, അതിനെക്കാൾ 1 വലുതാണ്. തുടർച്ചയായി n-1 സംഖ്യയാണ് അറേയുടെ ഏറ്റവും വലിയ ഘടകം.

ഉദാഹരണം

arr[]={20,10,35,42,8}
2 1 3 4 0

വിശദീകരണം: കുറച്ച ഫോമിൽ അറേ നമ്പർ 0-നുള്ളിൽ n-1 ശ്രേണിയിൽ സ്ഥാപിക്കണം. നമുക്ക് 8 ചെറുതായി കാണാനാകും, അതിനാൽ ഇത് 0. 10 ആണ് അടുത്തത്, അതിനാൽ ഇത് 1, 20 എന്നത് 2 എന്നിങ്ങനെയാണ്.

 

ഒരു അറേ കുറച്ച ഫോമിലേക്ക് പരിവർത്തനം ചെയ്യുന്നതിനുള്ള അൽഗോരിതം

1. Declare a temporary array of size the same as the original array.
2. Copy all the values of the given array into the declared array.
3. Sort that array in which we have copied the value of the original array.
4. Declare a map and set an integer variable ‘val’ to 0.
5. Traverse the array and store the value of the temp array’ element as a key into the map and a val value and increasing the count of ‘val’ by 1 every time.
6. Traverse the original array from 0 to n-1.
  1. Place the value of the map’s key into the array.
7. Print the original array in which we replace the value of the map.

വിശദീകരണം

ഞങ്ങൾ ഒരു സംഖ്യ പൂർണ്ണസംഖ്യ നൽകി, യഥാർത്ഥ അറേയിലെ ഓരോ സംഖ്യയും ശ്രേണിയിൽ നിന്ന് ഒരു മൂല്യവും നഷ്‌ടപ്പെടുത്താതെ 0 മുതൽ n-1 വരെയുള്ള ശ്രേണി എടുക്കുന്ന തരത്തിൽ ഞങ്ങൾ ശ്രേണി കുറയ്‌ക്കേണ്ടതുണ്ട്. ഇതിനർത്ഥം നമ്മൾ അറേയിൽ 5 അക്കങ്ങൾ നൽകിയിട്ടുണ്ടെങ്കിൽ, ഒറിജിനൽ അറേയിലെ ഒരു ഘടകത്തിന്റെ ഓരോ സ്ഥാനത്തും 0 മുതൽ 4 വരെ സംഖ്യ ഉൾപ്പെടുത്തും.

അതിനായി, n വലുപ്പത്തിന്റെ ഒരു അധിക ശ്രേണി ഞങ്ങൾ ഉപയോഗിക്കും, നമ്മൾ ചെയ്യാൻ പോകുന്നത് യഥാർത്ഥ അറേയിൽ നിന്ന് യഥാർത്ഥ അറേ പകർത്തും എന്നതാണ്. കാരണം ഞങ്ങൾ അതിൽ പ്രവർത്തനം നടത്താൻ പോകുന്നു. ഞങ്ങൾ‌ പകർ‌ത്തിയ അറേ കുറയ്‌ക്കാത്ത ക്രമത്തിൽ‌ അടുക്കും. കാരണം, ഓരോ ഘടകത്തെയും തന്നിരിക്കുന്ന ശ്രേണിയിൽ നിന്ന് അനുയോജ്യമായ ഒരു സംഖ്യയിലേക്ക് ചുരുക്കണം. ഞങ്ങൾ ഒരു മാപ്പും വേരിയബിളും എന്ന് വിളിക്കും 'val' 0 ലേക്ക്.

ഒരു കീ ആയി ഞങ്ങൾ സൃഷ്ടിച്ച താൽക്കാലിക അറേയുടെ മൂല്യങ്ങൾ മാപ്പ് സംഭരിക്കാൻ പോകുന്നു, ഇപ്പോൾ താൽക്കാലിക അറേയും അടുക്കിയിരിക്കുന്നു, അതിനാൽ നമുക്ക് o മുതൽ n-1 വരെ നമ്പർ സ്ഥാപിക്കാൻ കഴിയും. ഞങ്ങൾ അറേയിലൂടെ സഞ്ചരിച്ച് ഘടകങ്ങളെ കീ ആയി സ്ഥാപിക്കും Val കീയുടെ മൂല്യത്തിലേക്ക്. ന്റെ മൂല്യം Val ഒരു പുതിയ മൂല്യവുമായി സഞ്ചരിക്കുമ്പോഴെല്ലാം ഞങ്ങൾ 1 വർദ്ധിക്കും, അതിനാൽ ഇത് യാന്ത്രികമായി 0 മുതൽ n-1 വരെയാണ്.

യഥാർത്ഥ അറേയിലൂടെ സഞ്ചരിച്ച് മാപ്പിന്റെ എല്ലാ മൂല്യങ്ങളും യഥാർത്ഥ അറേയിലേക്ക് തിരുകുക അല്ലെങ്കിൽ യഥാർത്ഥ അറേയെ ഈ പുതിയ മൂല്യങ്ങൾ ഉപയോഗിച്ച് മാറ്റിസ്ഥാപിക്കുമെന്ന് നമുക്ക് പറയാം. ഒറിജിനൽ അറേയിലെ ആ ഘടകങ്ങൾ ഞങ്ങൾ ഇതിനകം 0 മുതൽ n-1 വരെയുള്ള ശ്രേണിയിലേക്ക് ചുരുക്കിയതിനാൽ പ്രിന്റുചെയ്യുക.

കുറച്ച ഫോമിലേക്ക് ഒരു ശ്രേണി പരിവർത്തനം ചെയ്യുക

കോഡ്

ഒരു അറേ കുറച്ച ഫോമിലേക്ക് പരിവർത്തനം ചെയ്യുന്നതിനുള്ള സി ++ കോഡ്

#include<iostream>
#include<unordered_map>
#include<algorithm>

using namespace std;

void convert(int arr[], int n)
{
    int temp[n];
    memcpy(temp, arr, n*sizeof(int));

    sort(temp, temp + n);

    unordered_map<int, int> umap;

    int val = 0;
    for (int i = 0; i < n; i++)
        umap[temp[i]] = val++;

    for (int i = 0; i < n; i++)
        arr[i] = umap[arr[i]];
}
void printArr(int arr[], int n)
{
    for (int i=0; i<n; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = {20,10,35,42,8};
    int n = sizeof(arr)/sizeof(arr[0]);

    convert(arr, n);
    cout << "Converted Array is : \n";
    printArr(arr, n);
    return 0;
}
Converted Array is :
2 1 3 4 0

 

ഒരു അറേ കുറച്ച ഫോമിലേക്ക് പരിവർത്തനം ചെയ്യുന്നതിനുള്ള ജാവ കോഡ്

import java.util.HashMap;
import java.util.Arrays;

class ReducedArray
{
    public static void convert(int arr[], int n)
    {
        int temp[] = arr.clone();

        Arrays.sort(temp);

        HashMap<Integer, Integer> umap = new HashMap<>();

        int val = 0;
        for (int i = 0; i < n; i++)
            umap.put(temp[i], val++);


        System.out.println("Converted Array is : ");
        for (int i = 0; i < n; i++)
        {
            arr[i] = umap.get(arr[i]);
            System.out.print(arr[i] + " ");
        }
    }
    public static void main(String[] args)
    {

        int arr[] = {20,10,35,42,8};
        int n = arr.length;
        convert(arr, n);

    }
}
Converted Array is :
2 1 3 4 0

 

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

We അടുക്കി ഞങ്ങളുടെ ഇൻപുട്ട് അറേ. അതുകൊണ്ടാണ് O (n ലോഗ് n) എവിടെ “N” അറേയുടെ വലുപ്പം.

ബഹിരാകാശ സങ്കീർണ്ണത

ഞങ്ങൾ ഒരു ഇൻപുട്ട് അറേ സംഭരിച്ചതിനാൽ ഞങ്ങൾ നേടി O (n) എവിടെ “N” അറേയുടെ വലുപ്പം.