Рубрики

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

Для заданного массива Q [] размера N — 1, такого, что каждый Q [i] = P [i + 1] — P [i], где P [] — премутация первых N натуральных чисел, задача состоит в том, чтобы найти это перестановка. Если допустимая перестановка P [] не найдена, выведите -1 .

Примеры:

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

Input: Q[] = {1, 1, 1, 1}
Output: 1 2 3 4 5

Подход: это математический алгоритмический вопрос. Обозначим P [i] = x . Следовательно, P [i + 1] = P [i] + (P [i + 1] — P [i]) = x + Q [i] (поскольку Q [i] = P [i + 1] — P [i] ] ).
Следовательно, P [i + 2] = P [i] + (P [i + 1] — P [i]) + (P [i + 2] — P [i + 1]) = x + Q [i] + Q [i + 1] . Заметьте, здесь формируется шаблон. P является ничем иным, как [x, x + Q [1], x + Q [1] + Q [2] +… + x + Q [1] + Q [2] +… + Q [n — 1]], где x = P [i], который до сих пор неизвестен.

Позволяет перестановку P ' где P' [i] = P [i] — x . Следовательно, P '= [0, Q [1], Q [1] + Q [2], Q [1] + Q [2] + Q [3],…, Q [1] + Q [2] + … + Q [n — 1]] .

Чтобы найти x , давайте найдем самый маленький элемент в P ' . Пусть это будет P '[k] . Следовательно, x = 1 — P '[k] . Это потому, что исходная перестановка P имеет целые числа от 1 до n, и поэтому 1 может быть минимальным элементом в P. Найдя x , добавьте x к каждому P ', чтобы получить исходную перестановку P.

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

C ++

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

using namespace std;

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

void findPerm(int Q[], int n)

{

  

    int minval = 0, qsum = 0;

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

  

        // Каждый элемент в P 'похож на

        // накопленная сумма в Q

        qsum += Q[i];

  

        // minval - это минимум

        // значение в P '

        if (qsum < minval)

            minval = qsum;

    }

    vector<int> P(n);

    P[0] = 1 - minval;

  

    // Чтобы проверить, если каждая запись в P

    // находится в диапазоне [1, n]

    bool permFound = true;

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

        P[i + 1] = P[i] + Q[i];

  

        // Неверная перестановка

        if (P[i + 1] > n || P[i + 1] < 1) {

            permFound = false;

            break;

        }

    }

  

    // Если существует допустимая перестановка

    if (permFound) {

  

        // Распечатать перестановку

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

            cout << P[i] << " ";

        }

    }

    else {

  

        // Нет действительной перестановки

        cout << -1;

    }

}

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

int main()

{

    int Q[] = { -2, 1 };

    int n = 1 + (sizeof(Q) / sizeof(int));

  

    findPerm(Q, n);

  

    return 0;

}

Джава

// Java реализация подхода

  

class GFG

{

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

static void findPerm(int Q[], int n)

{

  

    int minval = 0, qsum = 0;

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

    {

  

        // Каждый элемент в P 'похож на

        // накопленная сумма в Q

        qsum += Q[i];

  

        // minval - это минимум

        // значение в P '

        if (qsum < minval)

            minval = qsum;

    }

    int []P = new int[n];

    P[0] = 1 - minval;

  

    // Чтобы проверить, если каждая запись в P

    // находится в диапазоне [1, n]

    boolean permFound = true;

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

    {

        P[i + 1] = P[i] + Q[i];

  

        // Неверная перестановка

        if (P[i + 1] > n || P[i + 1] < 1)

        {

            permFound = false;

            break;

        }

    }

  

    // Если существует допустимая перестановка

    if (permFound)

    {

  

        // Распечатать перестановку

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

        {

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

        }

    }

    else 

    {

  

        // Нет действительной перестановки

        System.out.print(-1);

    }

}

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

public static void main(String[] args)

{

    int Q[] = { -2, 1 };

    int n = 1 + Q.length;

  

    findPerm(Q, n);

  
}
}

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

python3

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

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

def findPerm(Q, n) : 

  

    minval = 0; qsum = 0

    for i in range(n - 1) :

  

        # Каждый элемент в P 'похож на

        # накопленная сумма в Q

        qsum += Q[i]; 

  

        # minval - это минимум

        # значение в P '

        if (qsum < minval) :

            minval = qsum; 

  

    P = [0]*n; 

    P[0] = 1 - minval; 

  

    # Чтобы проверить, если каждая запись в P

    # находится в диапазоне [1, n]

    permFound = True

      

    for i in range(n - 1) :

        P[i + 1] = P[i] + Q[i]; 

  

        # Неверная перестановка

        if (P[i + 1] > n or P[i + 1] < 1) :

            permFound = False

            break

  

    # Если существует допустимая перестановка

    if (permFound) :

  

        # Распечатать перестановку

        for i in range(n) :

            print(P[i],end=" "); 

    else :

  

        # Нет действительной перестановки

        print(-1); 

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

if __name__ == "__main__"

  

    Q = [ -2, 1 ]; 

    n = 1 + len(Q) ;

  

    findPerm(Q, n); 

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

C #

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

using System;

using System.Collections.Generic;

  

class GFG

{

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

static void findPerm(int []Q, int n)

{

  

    int minval = 0, qsum = 0;

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

    {

  

        // Каждый элемент в P 'похож на

        // накопленная сумма в Q

        qsum += Q[i];

  

        // minval - это минимум

        // значение в P '

        if (qsum < minval)

            minval = qsum;

    }

    int []P = new int[n];

    P[0] = 1 - minval;

  

    // Чтобы проверить, если каждая запись в P

    // находится в диапазоне [1, n]

    bool permFound = true;

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

    {

        P[i + 1] = P[i] + Q[i];

  

        // Неверная перестановка

        if (P[i + 1] > n || P[i + 1] < 1)

        {

            permFound = false;

            break;

        }

    }

  

    // Если существует допустимая перестановка

    if (permFound)

    {

  

        // Распечатать перестановку

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

        {

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

        }

    }

    else

    {

  

        // Нет действительной перестановки

        Console.Write(-1);

    }

}

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

public static void Main(String[] args)

{

    int []Q = { -2, 1 };

    int n = 1 + Q.Length;

  

    findPerm(Q, n);

}
}

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

Выход:

3 1 2

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

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

0.00 (0%) 0 votes