Рубрики

Преобразовать массив в уменьшенную форму | Набор 1 (простой и хэширующий)

Учитывая массив с n различными элементами, преобразовать данный массив в форму, где все элементы находятся в диапазоне от 0 до n-1. Порядок элементов одинаков, т. Е. 0 помещается вместо наименьшего элемента, 1 — для второго наименьшего элемента,… n-1 — для наибольшего элемента.

Input:  arr[] = {10, 40, 20}
Output: arr[] = {0, 2, 1}

Input:  arr[] = {5, 10, 40, 30, 20}
Output: arr[] = {0, 1, 4, 3, 2}

Ожидаемая сложность времени O (n Log n).

Мы настоятельно рекомендуем вам нажать здесь и попрактиковаться, прежде чем переходить к решению.

Способ 1 (простой)
Простое решение — сначала найти минимальный элемент, заменить его на 0, рассмотреть оставшийся массив и найти минимум в оставшемся массиве, заменить его на 1 и так далее. Временная сложность этого решения составляет O (n 2 )

Метод 2 (Эффективный)
Идея состоит в том, чтобы использовать хеширование и сортировку. Ниже приведены шаги.
1) Создайте временный массив и скопируйте содержимое данного массива в temp []. Это занимает O (N) время.
2) Сортировка temp [] в порядке возрастания. Это занимает O (n Log n) время.
3) Создать пустую хеш-таблицу. Это занимает O (1) время.
4) Traverse temp [] формируют слева направо и сохраняют отображение чисел и их значений (в преобразованном массиве) в хеш-таблицу. Это занимает в среднем O (N) времени.
5) Пройдите через данный массив и измените элементы на их позиции, используя хеш-таблицу. Это занимает в среднем O (N) времени.

Общая временная сложность этого решения составляет O (n Log n).

Ниже приведены реализации вышеуказанной идеи.

C ++

// C ++ программа для преобразования массива в уменьшенный
// форма
#include <bits/stdc++.h>

using namespace std;

  

void convert(int arr[], int n)

{

    // Создать временный массив и скопировать содержимое

    // из arr [] to temp

    int temp[n];

    memcpy(temp, arr, n*sizeof(int));

  

    // Сортировка временного массива

    sort(temp, temp + n);

  

    // Создать хеш-таблицу. обращаться

    // http://tinyurl.com/zp5wgef

    unordered_map<int, int> umap;

  

    // Вставка элементов одного за другим

    // temp [] и присваиваем им значения от 0

    // к п-1

    int val = 0;

    for (int i = 0; i < n; i++)

        umap[temp[i]] = val++;

  

    // Конвертировать массив, заняв позиции из

    // umap

    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[] = {10, 20, 15, 12, 11, 50};

    int n = sizeof(arr)/sizeof(arr[0]);

  

    cout << "Given Array is \n";

    printArr(arr, n);

  

    convert(arr , n);

  

    cout << "\n\nConverted Array is \n";

    printArr(arr, n);

  

    return 0;

}

Джава

// Java-программа для преобразования массива
// в уменьшенном виде

import java.util.*;

  

class GFG 

{

    public static void convert(int arr[], int n)

    {

        // Создать временный массив и скопировать содержимое

        // из arr [] to temp

        int temp[] = arr.clone();

  

        // Сортировка временного массива

        Arrays.sort(temp);

  

        // Создать хеш-таблицу.

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

  

        // Вставка элементов одного за другим

        // temp [] и присваиваем им значения от 0

        // к п-1

        int val = 0;

        for (int i = 0; i < n; i++)

            umap.put(temp[i], val++);

  

        // Конвертировать массив, заняв позиции из

        // umap

        for (int i = 0; i < n; i++)

            arr[i] = umap.get(arr[i]);

    }

  

    public static void printArr(int arr[], int n)

    {

        for (int i = 0; i < n; i++)

            System.out.print(arr[i] + " ");

    }

  

    // Код драйвера

    public static void main(String[] args) 

    {

  

        int arr[] = {10, 20, 15, 12, 11, 50};

        int n = arr.length;

  

        System.out.println("Given Array is ");

        printArr(arr, n);

  

        convert(arr , n);

  

        System.out.println("\n\nConverted Array is ");

        printArr(arr, n);

  

    }

}

  
// Этот код предоставлен Abhishek Panwar

python3

# Python3 программа для преобразования массива
# в сокращенном виде

def convert(arr, n):

    # Создать временный массив и скопировать содержимое

    № обр. [] в темп

    temp = [arr[i] for i in range (n) ]

      

    # Сортировать временный массив

    temp.sort()

      

    # создать карту

    umap = {}

      

      

    # Один за другим вставлять отсортированные элементы

    # temp [] и присваивать им значения от 0

    # до n-1

    val = 0

    for i in range (n):

        umap[temp[i]] = val

        val += 1

      

    # Конвертировать массив, заняв позиции из umap

    for i in range (n):

        arr[i] = umap[arr[i]]

      

def printArr(arr, n):

    for i in range(n):

        print(arr[i], end = " ")

  
Код водителя

if __name__ == "__main__":

    arr = [10, 20, 15, 12, 11, 50]

    n = len(arr)

    print("Given Array is ")

    printArr(arr, n)

    convert(arr , n)

    print("\n\nConverted Array is ")

    printArr(arr, n)

  
# Этот код предоставлен Abhishek Gupta


Выход :

Given Array is 
10 20 15 12 11 50 

Converted Array is 
0 4 3 2 1 5 

Преобразовать массив в уменьшенную форму | Набор 2 (Используя вектор пар)

Эта статья предоставлена Dheeraj Gupta . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Преобразовать массив в уменьшенную форму | Набор 1 (простой и хэширующий)

0.00 (0%) 0 votes