Βρείτε ζεύγη με δεδομένο άθροισμα έτσι ώστε τα στοιχεία του ζεύγους να βρίσκονται σε διαφορετικές σειρές


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις αμαζόνα DE Shaw Σκηνοθεσία GreyOrange Πράγματι Pinterest Τερατάτα
Παράταξη Χασίσι Μήτρα

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

"Βρείτε ζεύγη με δεδομένο άθροισμα έτσι ώστε τα στοιχεία του ζεύγους να βρίσκονται σε διαφορετικές σειρές" Το πρόβλημα δηλώνει ότι σας δίνεται ένας πίνακας ακέραιων αριθμών και μια τιμή που ονομάζεται "άθροισμα". Η δήλωση προβλήματος ζητά να ανακαλύψει όλα τα ζεύγη σε έναν πίνακα που συνοψίζει μια δεδομένη τιμή που ονομάζεται άθροισμα και επίσης και οι δύο αριθμοί πρέπει να προέρχονται από διαφορετική σειρά. (Και οι δύο αριθμοί δεν πρέπει να είναι από την ίδια σειρά).

Παράδειγμα

int matrix[][]= {{3, 4, 7, 2},

{8, 9, 1, 10},

{5, 4, 0, 4},

{12, 0, 1, 13}};



sum = 15
(3, 12), (7, 8), (2, 13), (10, 5)

Επεξήγηση: Κάθε ένας από τους αριθμούς κάθε ζεύγους είναι από διαφορετική σειρά.

Αλγόριθμος για την εύρεση ζευγών με δεδομένο άθροισμα έτσι ώστε τα στοιχεία του ζεύγους να βρίσκονται σε διαφορετικές σειρές

1. Declare a map.
2. Put all the values of the matrix into the map with their row and column index.
3. Traverse the matrix.
  1. Set the remainingValue to the difference of sum and each value of the matrix.
  2. Check if the map contains the value of remainingValue if true then get its row and column index which we already put it into the map.
    1. Check if this row value is not equal to current i and also a row is greater than i.
      1. If true then print the matrix[i][j] and matrix[row][column].
4. Keep repeating the process until the whole matrix is traversed.

εξήγηση

Μας δίνεται μια μήτρα ακεραίων. Πρέπει να μάθουμε όλα τα ζεύγη σε έναν πίνακα έτσι ώστε το στοιχείο κάθε ζεύγους να έχει ένα άθροισμα ίσο με τη δεδομένη τιμή. Και επίσης υπάρχει μια συνθήκη, οι αριθμοί που επιλέγουμε σε ένα ζεύγος πρέπει να είναι από τη διαφορετική σειρά ενός πίνακα. Αν συνεχίσουμε να το λύνουμε με την αφελής προσέγγιση. Και διασχίζοντας κάθε σειρά στο στοιχείο τότε θα χρειαζόταν O (n4). Θα το λύσουμε χρησιμοποιώντας το κατακερματισμό ή Χάρτης / HashMap. Θα δηλώνουμε έναν χάρτη. Ξεκινήστε να διασχίζετε τη μήτρα και τοποθετήστε τα στοιχεία του πίνακα στο χάρτη ως κλειδί. Και το ευρετήριο της γραμμής και της στήλης του στοιχείου του πίνακα.

Μπορούμε να βάλουμε την τιμή του ευρετηρίου γραμμών και στηλών σε έναν χάρτη χρησιμοποιώντας τη μέθοδο make_pair στο C ++. Ή εάν χρησιμοποιούμε java μπορούμε να δημιουργήσουμε απλά μια τάξη και αυτό είναι αντικείμενα κατηγορίας που μπορούμε να την αποθηκεύσουμε στον χάρτη. Αργότερα, εάν πρέπει να πάρουμε αυτήν την τιμή, θα χρησιμοποιήσουμε αυτό το αντικείμενο κλάσης για να πάρουμε αυτές τις τιμές γραμμής και στήλης.

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

Βρείτε ζεύγη με δεδομένο άθροισμα έτσι ώστε τα στοιχεία του ζεύγους να βρίσκονται σε διαφορετικές σειρές

Κώδικας

Κωδικός C ++ για να βρείτε ζεύγη με δεδομένο άθροισμα έτσι ώστε τα στοιχεία του ζεύγους να βρίσκονται σε διαφορετικές σειρές

#include<iostream>
#include<unordered_map>

using namespace std;

const int MAX = 100;

void makePairWithGivenSum (int matrix[][MAX], int n, int sum)
{
    unordered_map<int, pair<int, int> > MAP;
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            MAP[matrix[i][j]] = make_pair(i, j);

    for (int i=0; i<n; i++)
    {
        for (int j=0; j<n; j++)
        {
            int remainingSum = sum - matrix[i][j];
            auto it = MAP.find(remainingSum);

            if (it != MAP.end())
            {
                pair<int, int> p = it->second;
                int row = p.first, col = p.second;
                if (row != i && row > i)
                    cout << "(" << matrix[i][j] << ", "
                         << matrix[row][col] << "), ";
            }
        }
    }
}
int main()
{
    int n = 4, sum = 11;
    int matrix[][MAX]= {{3, 4, 7, 2},
        {8, 9, 1, 10},
        {5, 4, 0, 4},
        {12, 0, 1, 13}
    };
    makePairWithGivenSum (matrix, n, sum);
    return 0;
}
(3, 8), (7, 4), (2, 9), (10, 1),

Κωδικός Java για να βρείτε ζεύγη με δεδομένο άθροισμα έτσι ώστε τα στοιχεία του ζεύγους να βρίσκονται σε διαφορετικές σειρές

import java.util.HashMap;
class Pair
{
    int first, second;
    Pair(int first, int second)
    {
        this.first=first;
        this.second=second;
    }
}
class pairSum
{
    public static void makePairWithGivenSum(int matrix[][], int n, int sum)
    {
        HashMap<Integer, Pair > MAP=new HashMap<Integer, Pair>();
        for (int i=0; i<n; i++)
        {
            for (int j=0; j<n; j++)
            {
                MAP.put(matrix[i][j], new Pair(i,j));
            }
        }
        for (int i=0; i<n; i++)
        {
            for (int j=0; j<n; j++)
            {
                int remainingSum = sum - matrix[i][j];

                if (MAP.containsKey(remainingSum))
                {
                    Pair p = MAP.get(remainingSum);
                    int row = p.first, col = p.second;
                    if (row != i && row > i)
                        System.out.print("(" + matrix[i][j] + ", " + matrix[row][col] + "), ");

                }
            }
        }
    }
    public static void main(String [] args)
    {
        int n = 4, sum = 15;
        int matrix[][]= {{3, 4, 7, 2},
            {8, 9, 1, 10},
            {5, 4, 0, 4},
            {12, 0, 1, 13}
        };
        makePairWithGivenSum (matrix, n, sum);
    }
}
(3, 12), (7, 8), (2, 13), (10, 5),

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

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

Διασχίζουμε τη μήτρα και αφού χρησιμοποιούμε το HashMap, είμαστε σε θέση να το πετύχουμε Επί2όπου «Ν» είναι ο αριθμός των στοιχείων στη μήτρα.

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

ΕΠΙ) όπου "N" είναι ο αριθμός των στοιχείων στη μήτρα.