Βρείτε τέσσερα στοιχεία που συνοψίζουν μια δεδομένη τιμή (Hashmap)


Επίπεδο δυσκολίας Σκληρά
Συχνές ερωτήσεις αμαζόνα Google Microsoft
Παράταξη Χασίσι Ταξινόμηση

Το πρόβλημα "Βρείτε τέσσερα στοιχεία που συνοψίζουν μια δεδομένη τιμή (Hashmap)" δηλώνει ότι υποθέστε ότι έχετε έναν ακέραιο πίνακα και έναν αριθμό που ονομάζεται άθροισμα. Η δήλωση προβλήματος ζητά να προσδιοριστεί εάν υπάρχουν τέσσερα στοιχεία στον πίνακα που συνοψίζουν τη δεδομένη τιμή "άθροισμα". Εάν είναι αλήθεια, τότε η συνάρτηση εξάγει «Ναι», αλλιώς εξάγει «Όχι».

Παράδειγμα

Βρείτε τέσσερα στοιχεία που συνοψίζουν μια δεδομένη τιμή (Hashmap)

arr[] = {2, 7, 3, 2, 9, 5, 9, 3}
sum=25
Yes
arr[] = {4, 3, 1, 6, 8, 5, 4, 1}
sum=30
No

Αλγόριθμος

  1. Διασχίστε το βρόχο, ενώ εγώ <n - 1.
    1. Διασχίστε το βρόχο, ενώ j = i + 1 <n
      1. Αποθηκεύστε την τιμή arr [i] + arr [j] σε val και ελέγξτε αν υπάρχει άθροισμα val στον πίνακα κατακερματισμού.
        1. Εάν είναι αλήθεια, πάρτε το κλειδί και ανακαλύψτε τον αριθμό και επιστρέψτε το αληθινό.
      2. Διαφορετικά, βάλτε τα i και j στον πίνακα κατακερματισμού μαζί με το κλειδί ως arr [i] + arr [j].
  2. Επιστροφή ψευδής.

εξήγηση

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

Ας εξετάσουμε ένα παράδειγμα:

Παράδειγμα

arr [] = {2, 7, 3, 2, 9, 5, 9, 3}, άθροισμα = 25

Εδώ έχουμε πάρει ένα παράδειγμα. Έχουμε δηλώσει ένα Boolean συνάρτηση που πρόκειται να επιστρέψει αληθινή και ψευδή. Θα χρησιμοποιήσουμε επίσης την ιδιότητα αντικειμένων των οποίων αντικείμενα πρόκειται να χρησιμοποιήσουμε, στον χάρτη μας, καθώς ένα από τα επιχειρήματά μας είναι οποιαδήποτε λίστα ή διάνυσμα. Βασικά λοιπόν πρόκειται να διασχίσουμε τις συστοιχίες, αλλά παίρνοντας κάθε στοιχείο μιας συστοιχίας ταυτόχρονα σε έναν εξωτερικό βρόχο και διασχίζοντας τα υπόλοιπα στοιχεία που έρχονται με ένα δείκτη μπροστά, με τον δεύτερο εσωτερικό βρόχο.

Παίρνουμε το άθροισμα και των δύο στοιχείων που είναι arr [i] + arr [j] και το αποθηκεύουμε σε κάποια μεταβλητή που ονομάζεται val και στη συνέχεια ελέγχουμε εάν το άθροισμα-val υπάρχει στο hashtable ή όχι, αν δεν υπάρχει, απλώς σπρώξτε τα στοιχεία στο χάρτη, ας υποθέσουμε ότι έχουμε τα στοιχεία 2 και 7 του πίνακα (arr [i] και arr [j]) το άθροισμα είναι 9 και το άθροισμα που είναι 25-9 είναι 18 είναι δεν υπάρχει στον πίνακα κατακερματισμού, οπότε απλώς πατάμε 9 και τρέχοντα ευρετήρια που είναι 0 και 1, ώστε αργότερα να μπορούμε να μάθουμε αν το άθροισμα-arr [i] + arr [j] υπάρχει ή όχι στον πίνακα. Εάν υπάρχει, πάρτε απλώς τις τιμές του κλειδιού και ελέγξτε μερικές προϋποθέσεις σε αυτό, αν είναι ικανοποιημένος, επιστρέψτε αληθινός. Σημαίνει ότι βρήκαμε την απάντησή μας.

Κωδικός C ++ για να βρείτε τέσσερα στοιχεία που συνοψίζουν μια δεδομένη τιμή (Hashmap)

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

typedef pair<int, int> Pair;

bool getFourNumber(int arr[], int n, int sum)
{
    unordered_map<int, vector<Pair>> map;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            int val = sum - (arr[i] + arr[j]);
            if (map.find(val) != map.end())
            {
                for (auto pair : map.find(val)->second)
                {
                    int x = pair.first;
                    int y = pair.second;
                    if ((x != i && x != j) && (y != i && y != j))
                    {
                        return true;
                    }
                }
            }
            map[arr[i] + arr[j]].push_back({i, j});
        }
    }
    return false;
}
int main()
{
    int arr[] = { 2, 7, 3, 2, 9, 5, 9, 3 };
    int sum = 25;
    int n = sizeof(arr) / sizeof(arr[0]);
    if(getFourNumber(arr, n, sum))
        cout << "Yes";
    else
        cout<<"No";
    return 0;
}
Yes

Κωδικός Java για να βρείτε τέσσερα στοιχεία που συνοψίζουν μια δεδομένη τιμή (Hashmap)

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Pair
{
    public int x, y;
    Pair(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
}
class printQuadruplets
{
    public static boolean getFourNumber(int[] arr, int n, int sum)
    {
        Map<Integer, List<Pair>> map = new HashMap<>();
        for (int i = 0; i < n - 1; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                int val= (arr[i] + arr[j]);
                if (map.containsKey(sum-val))
                {
                    for (Pair pair : map.get(sum-val))
                    {
                        int x = pair.x;
                        int y = pair.y;
                        if ((x != i && x != j) && (y != i && y != j))
                        {
                            return true;
                        }
                    }
                }
                map.putIfAbsent(arr[i] + arr[j], new ArrayList<>());
                map.get(arr[i] + arr[j]).add(new Pair(i, j));
            }
        }
        return false;
    }
    public static void main(String[] args)
    {
        int arr[] = { 2, 7, 3, 2, 9, 5, 9, 3 };
        int sum = 25;
        if (getFourNumber(arr, arr.length, sum))
        {
            System.out.println("Yes");
        }
        else
            System.out.println("No");
    }
}
Yes

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

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

Επί2όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα. Η χρήση του HashMap μας επέτρεψε να επιτύχουμε αυτήν την χρονική πολυπλοκότητα αλλιώς δεν θα ήταν δυνατόν.

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

Επί2όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα. Στη χειρότερη περίπτωση μπορεί να υπάρχουν N ^ 2 ζεύγη που πρέπει να αποθηκευτούν στο χάρτη. Έτσι, η διαστημική πολυπλοκότητα είναι πολυώνυμη.