Рубрики

Генерация исходного массива из разницы между каждыми двумя последовательными элементами

Дано N — 1 различий между двумя последовательными элементами массива, содержащего N чисел, которые находятся в диапазоне от 1 до N. Задача состоит в том, чтобы определить исходный массив, используя заданные различия. Если возможно, выведите массив, иначе выведите -1 .

Примеры:

Input: diff[] = {2, -3, 2}
Output: arr[] = {2, 4, 1, 3}
4 – 2 = 2
1 – 4 = -3
3 – 1 = 2

Input: diff[] = {2, 2, 2}
Output: -1

Подход: поскольку мы хотим генерировать перестановки в диапазоне [1, n], и каждая цифра должна встречаться только один раз. Взять, к примеру,

arr[] = {2, -3, 2}
Here, P2 – P1 = 2, P3 – P2 = -3, P4 – P3 = 2.
Let P1 = x then P2 = x + 2, P3 = P2 – 3 = x + 2 – 3 = x – 1, P4 = P3 + 2 = x – 1 + 2 = x + 1.
So, P1 = x, P2 = x + 2, P3 = x – 1, P4 = x + 1.

Now since we want a permutation from 1 to n, therfore the P[i]’s we get above must also satisfy the condition. Since the value must be satisfied for each and every x, hence for our simplicity we take x = 0.
Now, P1 = 0, P2 = 2, P3 = -1, P4 = 1.

Мы отсортируем p [i] , после сортировки последовательная разница между каждым элементом должна быть равна 1. Если при любом индексе мы встречаем элемент p [i] такой, что p [i] — p [i — 1] ! = 1 тогда невозможно сгенерировать перестановку. Для генерации окончательной перестановки мы будем отслеживать индексы, для этого мы можем использовать map или unordered_map.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция для печати требуемой перестановки

void findPerm(int n, vector<int>& differences)

{

    vector<int> ans;

    ans.clear();

    ans.push_back(0);

  

    // Возьмем x = 0 для простоты

    int x = 0;

  

    // Рассчитать разницу

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

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

        int diff = differences[i];

        x = x + diff;

        ans.push_back(x);

    }

  

    // Сохраняем исходный массив

    vector<int> anss = ans;

    sort(ans.begin(), ans.end());

    int flag = -1;

  

    // Проверяем, нет ли последовательных элементов

    // есть разница = 1

    for (int i = 1; i <= n - 1; ++i) {

        int res = ans[i] - ans[i - 1];

        if (res != 1) {

            flag = 0;

        }

    }

  

    // Если последовательных элементов нет

    // разница 1 в любой позиции

    // ответ невозможен

    if (flag == 0) {

        cout << -1;

        return;

    }

  

    // Остальное храним индексы и значения

    // по этим показателям на карте

    // и напечатать их

    else {

        unordered_map<int, int> mpp;

        mpp.clear();

        int j = 1;

        vector<int> value_at_index;

        for (auto& x : ans) {

            mpp[x] = j;

            ++j;

        }

        for (auto& x : anss) {

            value_at_index.push_back(mpp[x]);

        }

        for (auto& x : value_at_index) {

            cout << x << " ";

        }

        cout << endl;

    }

}

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

int main()

{

    vector<int> differences;

    differences.push_back(2);

    differences.push_back(-3);

    differences.push_back(2);

    int n = differences.size() + 1;

    findPerm(n, differences);

  

    return 0;

}

Джава

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

import java.util.*;

class GFG 

{

  
// Функция для печати требуемой перестановки

static void findPerm(int n, Vector<Integer> differences)

{

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

    ans.clear();

    ans.add(0);

  

    // Возьмем x = 0 для простоты

    int x = 0;

  

    // Рассчитать разницу

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

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

    {

        int diff = differences.get(i);

        x = x + diff;

        ans.add(x);

    }

  

    // Сохраняем исходный массив

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

    for(Integer obj:ans)

        anss.add(obj);

          

    Collections.sort(ans);

    int flag = -1;

  

    // Проверяем, нет ли последовательных элементов

    // есть разница = 1

    for (int i = 1; i <= n - 1; ++i)

    {

        int res = ans.get(i) - ans.get(i - 1);

        if (res != 1

        {

            flag = 0;

        }

    }

  

    // Если последовательных элементов нет

    // разница 1 в любой позиции

    // ответ невозможен

    if (flag == 0

    {

        System.out.print(-1);

        return;

    }

  

    // Остальное храним индексы и значения

    // по этим показателям на карте

    // и напечатать их

    else 

    {

        Map<Integer,Integer> mpp = new HashMap<>();

        mpp.clear();

        int j = 1;

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

        for (Integer x1 : ans) 

        {

            mpp.put(x1, j);

            ++j;

        }

        for (Integer x2 : anss) 

        {

            value_at_index.add(mpp.get(x2));

        }

        for (Integer x3 : value_at_index)

        {

            System.out.print(x3 + " ");

        }

        System.out.println();

    }

}

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

public static void main(String[] args)

{

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

    differences.add(2);

    differences.add(-3);

    differences.add(2);

    int n = differences.size() + 1;

    findPerm(n, differences);

    }

}

  
// Этот код предоставлен 29AjayKumar

python3

# Python3 реализация подхода

  
# Функция для печати требуемой перестановки

def findPerm(n, differences):

    ans = []

    ans.append(0)

  

    # Для простоты возьмем x = 0

    x = 0

  

    # Рассчитать разницу

    # и сохранить его в векторе

    for i in range(n - 1):

        diff = differences[i]

        x = x + diff

        ans.append(x)

  

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

    anss = ans

    ans = sorted(ans)

    flag = -1

  

    # Проверьте, есть ли в последовательных элементах

    # есть разница = 1

    for i in range(1, n):

        res = ans[i] - ans[i - 1]

        if (res != 1):

            flag = 0

  

    # Если последовательных элементов нет

    # разница 1 в любой позиции

    # ответ невозможен

    if (flag == 0):

        print("-1")

        return

  

    # Остальное хранить индексы и значения

    # по этим показателям на карте

    # и аккуратно напечатать их

    else:

        mpp = dict()

        j = 1

        value_at_index = []

        for x in ans:

            mpp[x] = j

            j += 1

  

        for x in anss:

            value_at_index.append(mpp[x])

  

        for x in value_at_index:

            print(x, end = " ")

        print()

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

differences=[]

differences.append(2)

differences.append(-3)

differences.append(2)

n = len(differences) + 1

findPerm(n, differences)

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

Выход:

2 4 1 3

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

Генерация исходного массива из разницы между каждыми двумя последовательными элементами

0.00 (0%) 0 votes