Βρείτε τον ελάχιστο αριθμό πράξεων συγχώνευσης για να δημιουργήσετε έναν πίνακα palindrome


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις Απολύτως πλίθα αμαζόνα Fourkites
Παράταξη Άπληστος μαθηματικά

Δήλωση προβλήματος

Σας δίνεται ένα παράταξη ακέραιων αριθμών. Η δήλωση προβλήματος ζητά να βρει τον ελάχιστο αριθμό λειτουργιών συγχώνευσης για να δημιουργήσει έναν πίνακα palindrome, δηλαδή να μάθετε τον ελάχιστο αριθμό εργασιών συγχώνευσης που πρέπει να γίνουν στον πίνακα για να τον κάνετε ένα palindrome. Η συγχώνευση σημαίνει απλά ότι μπορούμε να αντικαταστήσουμε το άθροισμα των γειτονικών στοιχείων με το ίδιο το άθροισμα.

Παράδειγμα

arr[] = {1, 4, 6, 6, 5}
1

Επεξήγηση: Μπορούμε να συγχωνεύσουμε 1 και 4 με το άθροισμά τους, οπότε γίνεται 5 και ο πίνακας μας γίνεται {5, 6, 6, 5}, το οποίο είναι ένα παλινδρομή.

arr[] = {2,1,2,4,3}
2

Επεξήγηση: Μπορούμε να συγχωνεύσουμε 1 και 2 με το άθροισμά τους, έτσι γίνεται 3 και επίσης 2 και 4 μπορούν να συγχωνευτούν, έτσι ο πίνακας μας γίνεται {3, 6, 3}

 

Αλγόριθμος για την εύρεση του ελάχιστου αριθμού των πράξεων συγχώνευσης για τη δημιουργία ενός πίνακα palindrome

1. Set the value of output to 0.
2. Traverse the array from i = 0 and j = n – 1, to i < n( length of an array).
  1. If arr[i] is equal to arr[j]
    1. Do i++ and j--.
  2. If arr[i] > arr[j]
    1. Do j—
    2. Update and restore the value of arr[j] = arr[j] + arr[j+1].
    3. Increase the output’s value by 1.
  3. If arr[i] < arr[j],
    1. Increase the value of i.
    2. Update arr[i] = arr[i] + arr[i-1].
    3. Increase the output’s value by 1.
3. Return output.

 

εξήγηση

Έχουμε δώσει μια σειρά από ακέραιους αριθμούς. Ζητείται να μάθουμε τον ελάχιστο αριθμό συγχώνευση λειτουργίες που μπορούν να γίνουν στον πίνακα για να γίνει a παλίνδρομο πίνακας. Εδώ η συγχώνευση σημαίνει την προσθήκη δύο παρακείμενων τιμών και τις αντικαθιστά με το άθροισμά τους. Εδώ θα βρούμε τον αριθμό των εργασιών που πρέπει να γίνουν.

Πρόκειται να διασχίσουμε τον πίνακα από αριστερά και επίσης από δεξιά κάνοντας δύο δείκτες να δείχνουν τη θέση κάθε ευρετηρίου διασταύρωσης. Επιλέξαμε και τις δύο πλευρές γιατί πρέπει να ελέγξουμε αν είναι παλινδρομήσει ή όχι. Και στο palindrome και από τις δύο πλευρές, σύμφωνα με τους δείκτες, τα στοιχεία είναι ίδια όπως και στο palindrome string. Έτσι θα ελέγξουμε την τιμή των αντίθετων πλευρών και θα λειτουργήσουμε στους δείκτες τους. Στη συνέχεια εκτελούμε συγχωνεύσεις και συνεχίζουμε μέχρι να βρούμε τον αριθμό των συγχωνεύσεων που πρέπει να γίνουν.

Θα ελέγξουμε εάν το πρώτο στοιχείο από τα αριστερά και από τα δεξιά είναι ίσο. Στη συνέχεια, απλά μετακινήστε τους δείκτες προς το κέντρο της μονάδας. Ελέγξτε αν το στοιχείο δείκτη αριστερού δείκτη είναι μεγαλύτερο από το στοιχείο δείκτη δεξιού δείκτη και, στη συνέχεια, μειώστε την τιμή της τιμής του δεξιού δείκτη και ενημερώστε το arr [j] με το άθροισμα των παρακείμενων στοιχείων και αυξήστε την τιμή της εξόδου σημαίνει τον αριθμό μας λειτουργίες.

Θα ελέγξουμε εάν το στοιχείο δείκτη αριστερού δείκτη είναι μικρότερο από το στοιχείο δείκτη δεξιού δείκτη και, στη συνέχεια, θα αυξήσουμε την τιμή της τιμής αριστερού δείκτη και θα ενημερώσουμε το arr [i] με το άθροισμα των παρακείμενων στοιχείων και θα αυξήσουμε την τιμή της εξόδου σημαίνει αριθμός πράξεων. Και επιτέλους, θα επιστρέψουμε την τιμή εξόδου.

Βρείτε τον ελάχιστο αριθμό πράξεων συγχώνευσης για να δημιουργήσετε έναν πίνακα palindrome

Κωδικός για να βρείτε τον ελάχιστο αριθμό πράξεων συγχώνευσης για να δημιουργήσετε έναν πίνακα palindrome

Κωδικός C ++

#include<iostream>

using namespace std;

int getMinimumOperation(int arr[], int n)
{
    int output = 0;

    for (int i=0,j=n-1; i<=j;)
    {
        if (arr[i] == arr[j])
        {
            i++;
            j--;
        }
        else if (arr[i] > arr[j])
        {
            j--;
            arr[j] += arr[j+1] ;
            output++;
        }
        else
        {
            i++;
            arr[i] += arr[i-1];
            output++;
        }
    }
    return output;
}
int main()
{
    int arr[] = { 1, 4, 6, 6, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Minimum operations to be done: "<< getMinimumOperation(arr, n);
    return 0;
}
Minimum operations to be done: 1

 

Κωδικός Java

class ArrayPalindromeMerging
{
    public static int getMinimumOperation(int[] arr, int n)
    {
        int output = 0;
        for (int i=0,j=n-1; i<=j;)
        {
            if (arr[i] == arr[j])
            {
                i++;
                j--;
            }
            else if (arr[i] > arr[j])
            {
                j--;
                arr[j] += arr[j+1] ;
                output++;
            }
            else
            {
                i++;
                arr[i] += arr[i-1];
                output++;
            }
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = { 1, 4, 6, 6, 5} ;
        System.out.println("Minimum operations to be done : "+ getMinimumOperation(arr, arr.length));
    }
}
Minimum operations to be done : 1

 

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας

Απλώς διασχίζουμε τον πίνακα μία φορά, οπότε αυτό μετράει για την γραμμική πολυπλοκότητα του χρόνου. O (n) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα.

Διαστημική πολυπλοκότητα

Χρησιμοποιούμε απλώς έναν πίνακα που έχει μέγεθος n για την αποθήκευση της εισόδου, οπότε αυτός ο αλγόριθμος για την εύρεση του αριθμού των πράξεων συγχώνευσης για να κάνει έναν πίνακα palindrome έχει γραμμική πολυπλοκότητα χώρου. O (n) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα.