Рубрики

Подсчитать элементы, общие для обоих списков, но с разными ценами

Даны два списка list1 и list2, содержащие m и n элементов соответственно. Каждый элемент связан с двумя полями: имя и цена. Проблема заключается в подсчете товаров, которые есть в обоих списках, но с разными ценами.

Примеры:

Input : list1[] = {{"apple", 60}, {"bread", 20}, 
                   {"wheat", 50}, {"oil", 30}}
    list2[] = {{"milk", 20}, {"bread", 15}, 
                   {"wheat", 40}, {"apple", 60}}
Output : 2
bread and wheat are the two items common to both the
lists but with different prices.

Источник: Cognizant Интервью Опыт | Набор 5.

Метод 1 (Наивный подход): С помощью двух вложенных циклов сравнить каждый элемент list1 со всеми элементами list2. Если найдено совпадение с другой ценой, увеличьте счетчик .

CPP

// Реализация C ++ для подсчета элементов, общих для обоих
// списки но с разными ценами
#include <bits/stdc++.h>

  

using namespace std;

  
// детали товара

struct item

{

    string name;

    int price;

};

  
// функция для подсчета элементов, общих для обоих
// списки но с разными ценами

int countItems(item list1[], int m,

               item list2[], int n)

{

    int count = 0;

      

    // для каждого элемента «list1» проверяем, находится ли он в «list2»

    // но с другой ценой

    for (int i = 0; i < m; i++)    

        for (int j = 0; j < n; j++) 

  

            if ((list1[i].name.compare(list2[j].name) == 0) &&

                 (list1[i].price != list2[j].price))

                count++;        

      

    // необходимое количество предметов

    return count;

}

  
// Программа драйвера для тестирования выше

int main()

{

    item list1[] = {{"apple", 60}, {"bread", 20},

                    {"wheat", 50}, {"oil", 30}};

    item list2[] = {{"milk", 20}, {"bread", 15},

                   {"wheat", 40}, {"apple", 60}};

      

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

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

      

    cout << "Count = "    

         << countItems(list1, m, list2, n);

           

    return 0;     

python3

# Реализация Python для
# количество элементов, общих для обоих
# списки, но с разными
# Цены

  
# функция для подсчета предметов
# общее для обоих
# списки, но с разными ценами

def countItems(list1, list2):

    count = 0

      

    # для каждого элемента 'list1'

    # проверить, находится ли он в 'list2'

    # но с другой ценой

    for i in list1:

        for j in list2:

  

            if i[0] == j[0] and i[1] != j[1]:

                count += 1

      

    # необходимое количество предметов

    return count

  
# Программа драйвера для тестирования выше

list1 = [("apple", 60), ("bread", 20),

            ("wheat", 50), ("oil", 30)]

list2 = [("milk", 20), ("bread", 15),

            ("wheat", 40), ("apple", 60)]

      

print("Count = ", countItems(list1, list2))

      
# Этот код предоставлен Ансу Кумари.


Выход:

Count = 2

Сложность времени: O (m * n).
Вспомогательное пространство: O (1).

Метод 2 (бинарный поиск): сортировка списка 2 в алфавитном порядке по названию его элементов. Теперь для каждого элемента списка list1 проверьте, присутствует ли он в списке list2, используя технику бинарного поиска, и получите его цену из списка list2 . Если цены различаются, увеличивайте количество .

// Реализация C ++ для подсчета элементов, общих для обоих
// списки но с разными ценами
#include <bits/stdc++.h>

  

using namespace std;

  
// детали товара

struct item

{

    string name;

    int price;

};

  
// функция сравнения, используемая для сортировки

bool compare(struct item a, struct item b) 

{

    return (a.name.compare(b.name) <= 0);        

}

  
// функция для поиска 'str' в 'list2 []'. Если это существует, то
// цена, связанная со 'str' в 'list2 []'
// возвращено, иначе -1 возвращается. Здесь бинарный серач
// trechnique применяется для поиска

int binary_search(item list2[], int low, int high, string str)

{

    while (low <= high)

    {

        int mid = (low + high) / 2;

          

        // если true, элемент 'str' находится в 'list2'

        if (list2[mid].name.compare(str) == 0)

            return list2[mid].price;

          

        else if (list2[mid].name.compare(str) < 0)    

            low = mid + 1;

          

        else

            high = mid - 1;    

    }

      

    // элемент 'str' отсутствует в 'list2'

    return -1;

}

  
// функция для подсчета элементов, общих для обоих
// списки но с разными ценами

int countItems(item list1[], int m,

               item list2[], int n)

{

    // сортируем 'list2' в алфавитном порядке

    // название товара

    sort(list2, list2 + n, compare);

      

    // начальный счет

    int count = 0;

      

    for (int i = 0; i < m; i++) {

  

        // получаем цену товара list1 [i] из list2

        // если элемент отсутствует во втором списке, то

        // -1 получается

        int r = binary_search(list2, 0, n-1, list1[i].name);

          

        // если элемент присутствует в list2 с

        // другая цена

        if ((r != -1) && (r != list1[i].price))

            count++;

    }

      

    // необходимое количество предметов

    return count;

}

  
// Программа драйвера для тестирования выше

int main()

{

    item list1[] = {{"apple", 60}, {"bread", 20}, 

                     {"wheat", 50}, {"oil", 30}};

    item list2[] = {{"milk", 20}, {"bread", 15},

                   {"wheat", 40}, {"apple", 60}};

      

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

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

      

    cout << "Count = "    

         << countItems(list1, m, list2, n);

           

    return 0;     

}

Выход:

Count = 2

Сложность времени: (m * log 2 n).
Вспомогательное пространство: O (1).
Для эффективности список с максимальным количеством элементов должен быть отсортирован и использован для бинарного поиска.

Метод 3 (Эффективный подход): Создайте хеш-таблицу с кортежем (ключ, значение) как (наименование товара, цена) . Вставьте элементы list1 в хеш-таблицу. Теперь для каждого элемента списка list2 проверьте, является ли это хеш-таблицей или нет. Если он присутствует, то проверьте, отличается ли его цена от значения из хеш-таблицы. Если так, тогда увеличивайте количество .

// Реализация C ++ для подсчета элементов, общих для обоих
// списки но с разными ценами
#include <bits/stdc++.h>

  

using namespace std;

  
// детали товара

struct item

{

    string name;

    int price;

};

  
// функция для подсчета элементов, общих для обоих
// списки но с разными ценами

int countItems(item list1[], int m,

               item list2[], int n)

{

    // 'um' реализован как хеш-таблица, которая содержит

    // имя элемента в качестве ключа и цена в качестве значения

    // связано с ключом

    unordered_map<string, int> um;

    int count = 0;

      

    // вставляем элементы 'list1' в 'um'

    for (int i = 0; i < m; i++)

        um[list1[i].name] = list1[i].price;

      

    // для каждого элемента списка list2 проверяем,

    // присутствует в 'ит' с другой ценой

    // значение

    for (int i = 0; i < n; i++)    

        if ((um.find(list2[i].name) != um.end()) &&

            (um[list2[i].name] != list2[i].price))

            count++;

      

    // необходимое количество предметов

    return count;        

}

  
// Программа драйвера для тестирования выше

int main()

{

    item list1[] = {{"apple", 60}, {"bread", 20}, 

                    {"wheat", 50}, {"oil", 30}};

    item list2[] = {{"milk", 20}, {"bread", 15}, 

                    {"wheat", 40}, {"apple", 60}};

      

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

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

      

    cout << "Count = "    

         << countItems(list1, m, list2, n);

           

    return 0;     

}

Выход:

Count = 2

Сложность времени: O (m + n).
Вспомогательное пространство: O (м).
Для эффективности список с минимальным количеством элементов должен быть вставлен в хеш-таблицу.

Рекомендуемые посты:

Подсчитать элементы, общие для обоих списков, но с разными ценами

0.00 (0%) 0 votes