Μετρήστε τα κοινά στοιχεία και στις δύο λίστες αλλά με διαφορετικές τιμές


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις αμαζόνα Γεγονότα GE Healthcare Honeywell TCS Τέσλα
Δυαδική αναζήτηση Χασίσι Hashing Αναζήτηση

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

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

Παράδειγμα

List1[] = {{"egg", 60}, {"butter", 20}, {"rice", 50}, {oil", 30}}

List2[] = {{“butter", 20}, {"egg", 15},{"wheat", 40}, {"rice", 60}}
2

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

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

1. Declare a map and set the value of output to 0.
2. Store the first list’s name and its price to the map.
3. Traverse the second list.
    1. Check for the second list’s element, if each element’s name of the second list has a common value in list1’s name.
    2. Check for if that particular element’s price should not be equal to the element price in list1.
        1. If true, then increase the count of output by 1.
4. Return output.

εξήγηση

Μετρήστε τα κοινά στοιχεία και στις δύο λίστες αλλά με διαφορετικές τιμές

Δώσαμε δύο λίστες, κάθε μία από τις λίστες περιέχει την τιμή των δύο στηλών, περιέχει το όνομα οποιουδήποτε είδους και την τιμή του. Ο στόχος είναι να ανακαλυφθούν τα κοινά στοιχεία και στους δύο καταλόγους και επίσης οι τιμές τους δεν πρέπει να είναι ίσες μεταξύ τους σε σχέση με τα στοιχεία. Θα χρησιμοποιήσουμε κατακερματισμό και μια επιπλέον κατηγορία ή δομή, ενώ το κατακερματισμό παρέχει μια αποτελεσματική λύση.

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

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

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

Κωδικός C ++

#include<iostream>
#include<unordered_map>

using namespace std;

struct item
{
    string name;
    int price;
};
int getItemCount(item list1[], int m,item list2[], int n)
{
    unordered_map<string, int> MAP;
    int output = 0;

    for (int i = 0; i < m; i++)
        MAP[list1[i].name] = list1[i].price;

    for (int i = 0; i < n; i++)
        if ((MAP.find(list2[i].name) != MAP.end()) &&(MAP[list2[i].name] != list2[i].price))
            output++;

    return output;
}
int main()
{
    item list1[] = {{"egg", 60}, {"butter", 20}, {"rice", 50}, {"oil", 30}};
    item list2[] = {{"butter", 20}, {"egg", 15}, {"wheat", 40}, {"rice", 60}};

    int m = sizeof(list1) / sizeof(list1[0]);
    int n = sizeof(list2) / sizeof(list2[0]);

    cout<< getItemCount(list1, m, list2, n);

    return 0;
}
2

 

Κωδικός Java

import java.util.*;

class CountItems
{
    public static class item
    {
        String name;
        int price;
        item(String name, int price)
        {
            this.name=name;
            this.price=price;
        }
    };
    public static int getItemCount(item list1[], int m,item list2[], int n)
    {
        HashMap<String, Integer> MAP=new HashMap<>();
        int output = 0;

        for (int i = 0; i < m; i++)
        {
            MAP.put(list1[i].name, list1[i].price);

        }
        for (int i = 0; i < n; i++)
        {
            if ((MAP.containsKey(list2[i].name) && (MAP.get(list2[i].name) != list2[i].price)))
                output++;
        }
        return output;
    }
    public static void main(String [] args)
    {
        item list1[] = {new item("egg", 60), new item("butter", 20),new item("rice", 50), new item("oil", 30)};

        item list2[] = {new item("butter", 20), new item("egg", 15),new item("wheat", 40), new item("rice", 60)};
        int m = list1.length;
        int n = list2.length;
        System.out.println(getItemCount(list1, m, list2, n));

    }
}
2

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

Χρόνος πολυπλοκότητας για μέτρηση κοινών αντικειμένων με πρόβλημα διαφορετικών τιμών

O (m + n) όπου "M"   «Ν» είναι ο αριθμός των στοιχείων στη λίστα1 και στη λίστα2.

Διαστημική πολυπλοκότητα για μέτρηση κοινών αντικειμένων με πρόβλημα διαφορετικών τιμών

Δεδομένου ότι αποθηκεύουμε τα στοιχεία μόνο της λίστας 1 στον χάρτη, η πολυπλοκότητα του χώρου εξαρτάται μόνο από το μέγεθος της λίστας1. Έτσι, η πολυπλοκότητα του χώρου είναι Ο (μ) όπου "M" είναι ο αριθμός των στοιχείων στη λίστα.