Преобразуване на масив в намалена форма


Ниво на трудност M
Често задавани в LinkedIn Snapchat Xome Yahoo
Array Хашиш сортиране

Декларация за проблема

Проблемът „Преобразуване на масив в намалена форма“ гласи, че ви е даден масив от цели числа с размер 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, това, което ще направим, е да копираме оригиналния масив от оригиналния масив. Защото ще извършим операцията върху него. Ще сортираме копирания масив в не намаляващ ред. Защото трябва да направим всеки елемент редуциран до число, което е подходящо от дадения диапазон. Ще декларираме карта и променлива, наречена "вал" да 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) където "н" е размерът на масива.

Сложност на пространството

Тъй като съхранихме входен масив, постигнахме О (п) където "н" е размерът на масива.