Массивро ба шакли камкардашуда табдил диҳед


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад LinkedIn Snapchat Xome Yahoo
тартиботи ҳарбӣ Хаш Sorting

Изҳороти мушкилот

Масъалаи "Табдил додани массив ба шакли ихтисоршуда" изҳор медорад, ки ба шумо массиви бутуни андозаи 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 ва ғайра.

 

Алгоритми табдили массив ба шакли ихтисоршуда

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 -ро истифода мебарем, ки чӣ кор кунем, массиви аслиро аз массиви аслӣ нусхабардорӣ мекунем. Зеро мо амалиётро дар болои он анҷом медиҳем. Мо массиви нусхабардоршударо бо тартиби камшаванда ҷудо мекунем. Зеро мо бояд ҳар як унсурро ба як қатор табдил диҳем, ки аз доираи додашуда мувофиқ бошад. Мо харита ва тағирёбандаро бо номи эълон мекунем 'вал' ба 0.

Харита арзишҳои массиви муваққатиро, ки мо онро ҳамчун калид сохтаем, нигоҳ медорад ва ҳоло массиви муваққатӣ ҷобаҷо карда шудааст, то ки мо рақами аз o то n-1 ҷойгир карда тавонем. Мо массивро тай карда, элементҳоро ҳамчун калид ва ҷойгир мекунем Вал ба арзиши калид. Арзиши Вал ҳар вақте, ки мо бо арзиши нав мегузарем, мо 1 зиёд мешавем, аз ин рӯ он ба таври худкор аз 0 то n-1 фарқ мекунад.

Масви аслиро убур кунед ва ҳамаи арзишҳои харитаро ба массиви аслӣ гузоред, вагарна мо метавонем массиви аслиро бо ин қиматҳои нав иваз кунем. Он унсурҳои массиви аслиро чоп кунед, зеро мо онро аллакай ба шакли диапазони 0 то n-1 коҳиш додаем.

Массивро ба шакли камкардашуда табдил диҳед

рамз

Коди C ++ барои табдил додани массив ба шакли камкардашуда

#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

 

Рамзи Java барои табдил додани массив ба шакли камшуда

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 Log n) ки дар "Н" андозаи массив аст.

Мураккабии фазо

Азбаски мо массиви воридшударо нигоҳ доштем, ба даст овардем Эй (н) ки дар "Н" андозаи массив аст.