Пребројте ставке заједничке на обе листе, али са различитим ценама


Ниво тешкоће Лако
Често питани у амазонка Фацтсет ГЕ Хеалтхцаре Хонеивелл ТЦС Тесла
Бинарна претрага Хасх Хасхинг Претраживање

Изјава о проблему

Добили сте две листе. Сваки од којих индекс садржи назив предмета и његову цену. Изјава о проблему тражи да се преброје ставке заједничке на обе листе, али са различитим ценама, односно да се утврди колико је предмета заједничко на обе дате листе и такође по различитим ценама.

Пример

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, јер само морамо да избројимо број предмета и то радимо рачунајући број те уобичајене ставке и њену цену.

Шифра за бројање предмета заједничких на обе листе, али са различитим ценама

Ц ++ код

#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

 

Јава Цоде

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

Анализа сложености

Сложеност времена за бројање уобичајених предмета са различитим ценама

О (м + н) где "М"   „Н“ је број елемената у листи1 и листи2.

Сложеност простора за бројање уобичајених предмета са различитим ценама

Будући да на мапи чувамо само елементе листе 1, сложеност простора зависи само од величине листе1. Тако је сложеност простора О (м) где "М" је број елемената на листи.