Пребройте елементи, общи за двата списъка, но с различни цени


Ниво на трудност Лесно
Често задавани в Амазонка FactSet GE Healthcare Honeywell TCS Tesla
Двоично търсене Хашиш хеширане Търсене

Декларация за проблема

Дадени са ви два списъка. Всеки от които индекс съдържа името на артикула и цената му. Изложението на проблема изисква да се броят артикулите, общи за двата списъка, но с различни цени, което е да се установи колко броя артикули са общи в двата дадени списъка, а също и на различни цени.

Пример

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) където "Т" и "н" е броят на елементите в list1 и list2.

Сложност на пространството за преброяване на често срещани артикули с различни цени

Тъй като съхраняваме елементите само от списък 1 в картата, сложността на пространството зависи само от размера на list1. Така космическата сложност е O (m) където "Т" е броят на елементите в списъка.