Рубрики

Генерация исходного массива из массива, который хранит количество больших элементов справа

Для данного массива целых чисел больше [], в котором каждое значение массива представляет, сколько элементов больше, он находится справа от неизвестного массива arr []. Наша задача — создать оригинальный массив arr []. Можно предположить, что исходный массив содержит элементы в диапазоне от 1 до n, и все элементы являются уникальными
Примеры:

Input  : greater[] = { 6, 3, 2, 1, 0, 0, 0 }
Output : arr[] = [ 1, 4, 5, 6, 7, 3, 2 ]
 
Input  : greater[] = { 0, 0, 0, 0, 0 }
Output : arr[] = [ 5, 4, 3, 2, 1 ]  

Рассмотрим массив элементов temp [] = {1, 2, 3, 4, .. n}. Мы знаем, что значение больше [0] указывает количество элементов больше, чем arr [0]. Мы можем заметить, что (n — больший [0]) — й элемент temp [] может быть помещен в arr [0]. Поэтому мы помещаем это в arr [0] и удаляем это из temp []. Повторяем вышеописанный процесс для остальных элементов. Для каждого элемента больше [i] мы помещаем (n — больший [i] — i) -й элемент temp [] в arr [i] и удаляем его из temp [].

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

C ++

// C ++ программа для генерации исходного массива
// из массива, в котором хранится число
// большие элементы справа.
#include <bits/stdc++.h>

using namespace std;

  

void originalArray(int greater[], int n)

{

    // Массив, который используется для включения каждого

    // элемент только один раз

    vector<int> temp;

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

        temp.push_back(i);

  

    // Обход элемента массива

    int arr[n];

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

  

        // найти K-й (n-больший [i] -i)

        // наименьший элемент в Include_Array

        int k = n - greater[i] - i;

  

        arr[i] = temp[k];

  

        // удаляем текущий k-й элемент

        // из массива включения

        temp.erase(temp.begin() + k);

    }

  

    // выводим результирующий массив

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

        cout << arr[i] << " ";

}

  
// программа драйвера для проверки вышеуказанной функции

int main()

{

    int Arr[] = { 6, 3, 2, 1, 0, 1, 0 };

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

    originalArray(Arr, n);

    return 0;

}

Джава

// Java-программа для генерации исходного массива
// из массива, в котором хранится число
// большие элементы справа.

import java.util.Vector;

  

class GFG 

{

      

static void originalArray(int greater[], int n) 

    // Массив, который используется для включения каждого

    // элемент только один раз

    Vector<Integer> temp = new Vector<Integer>(); 

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

        temp.add(i); 

  

    // Обход элемента массива

    int arr[] = new int[n]; 

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

    

  

        // найти K-й (n-больший [i] -i)

        // наименьший элемент в Include_Array

        int k = n - greater[i] - i; 

  

        arr[i] = temp.get(k); 

  

        // удаляем текущий k-й элемент

        // из массива включения

        temp.remove(k); 

    

  

    // выводим результирующий массив

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

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

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

public static void main(String[] args)

{

    int Arr[] = { 6, 3, 2, 1, 0, 1, 0 }; 

    int n = Arr.length; 

    originalArray(Arr, n);

}

  
// Этот код предоставлен Rajput-Ji

python3

# Исходный массив программы Python3 из
# массив, в котором хранятся значения большего
# элементы справа

def originalArray(greater, n):

      

    # массив, который используется для включения

    # каждый элемент только один раз

    temp = []

      

    for i in range(n + 1):

        temp.append(i)

          

    # пройти элемент массива

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

      

    for i in range(n):

  

        # найти Kth (n-больше [i] -i)

        # наименьший элемент в Include_array

        k = n - greater[i] - i

          

        arr[i] = temp[k]

          

        # удалить текущий элемент kth

        # из включаемого массива

        del temp[k]

          

    for i in range(n):

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

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

arr = [6, 3, 2, 1, 0, 1, 0]

n = len(arr)

originalArray(arr, n)

  
# Этот код добавлен
# Мохит Кумар

C #

// C # программа для генерации исходного массива
// из массива, в котором хранится число
// большие элементы справа.

using System;

using System.Collections.Generic; 

  

class GFG 

{

      

static void originalArray(int []greater, int n) 

    // Массив, который используется для включения каждого

    // элемент только один раз

    List<int> temp = new List<int>(); 

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

        temp.Add(i); 

  

    // Обход элемента массива

    int []arr = new int[n]; 

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

    

  

        // найти K-й (n-больший [i] -i)

        // наименьший элемент в Include_Array

        int k = n - greater[i] - i; 

  

        arr[i] = temp[k]; 

  

        // удаляем текущий k-й элемент

        // из массива включения

        temp.RemoveAt(k); 

    

  

    // выводим результирующий массив

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

            Console.Write(arr[i] + " "); 

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

public static void Main()

{

    int []Arr = { 6, 3, 2, 1, 0, 1, 0 }; 

    int n = Arr.Length; 

    originalArray(Arr, n);

}

  
/ * Этот код предоставлен PrinciRaj1992 * /


Выход:

1 4 5 6 7 2 3

Сложность времени: (n 2 ) (операция удаления занимает O (n) в векторе)

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

Генерация исходного массива из массива, который хранит количество больших элементов справа

0.00 (0%) 0 votes