计算两个列表共有但价格不同的商品

本文概述

  • C ++
  • Java
  • Python3
  • C#
  • CPP
  • C ++
  • Java
  • C#
给出两个列表
列表1

list2
包含


?
项目。每个项目都与两个字段关联:名称和价格。问题是要计算两个列表中价格不同的商品。
例子:
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.

资源: 认知面试经验|设置5。
推荐:请尝试以下方法
{IDE}
【计算两个列表共有但价格不同的商品】首先, 在继续解决方案之前。
方法1(天真的方法):使用两个嵌套循环比较列表1与的所有项目list2。如果找到价格不同的匹配项, 则递增计数.
C ++
// C++ implementation to count items common to both // the lists but with different prices #include < bits/stdc++.h> using namespace std; // details of an item struct item { string name; int price; }; // function to count items common to both // the lists but with different prices int countItems(item list1[], int m, item list2[], int n) { int count = 0; // for each item of 'list1' check if it is in 'list2' // but with a different price 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++; // required count of items return count; } // Driver program to test above 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; }

Java
// Java implementation to count items common to both // the lists but with different prices class GFG{ // details of an item static class item { String name; int price; public item(String name, int price) { this .name = name; this .price = price; } }; // function to count items common to both // the lists but with different prices static int countItems(item list1[], int m, item list2[], int n) { int count = 0 ; // for each item of 'list1' check if it is in 'list2' // but with a different price for ( int i = 0 ; i < m; i++) for ( int j = 0 ; j < n; j++) if ((list1[i].name.compareTo(list2[j].name) == 0 ) & & (list1[i].price != list2[j].price)) count++; // required count of items return count; } // Driver code public static void main(String[] args) { item list1[] = { new item( "apple" , 60 ), new item( "bread" , 20 ), new item( "wheat" , 50 ), new item( "oil" , 30 )}; item list2[] = { new item( "milk" , 20 ), new item( "bread" , 15 ), new item( "wheat" , 40 ), new item( "apple" , 60 )}; int m = list1.length; int n = list2.length; System.out.print( "Count = " + countItems(list1, m, list2, n)); } } // This code is contributed by 29AjayKumar

Python3
# Python implementation to # count items common to both # the lists but with different # prices # function to count items # common to both # the lists but with different prices def countItems(list1, list2): count = 0# for each item of 'list1' # check if it is in 'list2' # but with a different price for i in list1: for j in list2: if i[ 0 ] = = j[ 0 ] and i[ 1 ] ! = j[ 1 ]: count + = 1# required count of items return count # Driver program to test above list1 = [( "apple" , 60 ), ( "bread" , 20 ), ( "wheat" , 50 ), ( "oil" , 30 )] list2 = [( "milk" , 20 ), ( "bread" , 15 ), ( "wheat" , 40 ), ( "apple" , 60 )]print ( "Count = " , countItems(list1, list2))# This code is contributed by Ansu Kumari.

C#
// C# implementation to count items common to both // the lists but with different prices using System; class GFG{// details of an item class item { public String name; public int price; public item(String name, int price) { this .name = name; this .price = price; } }; // function to count items common to both // the lists but with different prices static int countItems(item []list1, int m, item []list2, int n) { int count = 0; // for each item of 'list1' check if it is in 'list2' // but with a different price for ( int i = 0; i < m; i++) for ( int j = 0; j < n; j++)if ((list1[i].name.CompareTo(list2[j].name) == 0) & & (list1[i].price != list2[j].price)) count++; // required count of items return count; }// Driver code public static void Main(String[] args) { item []list1 = { new item( "apple" , 60), new item( "bread" , 20), new item( "wheat" , 50), new item( "oil" , 30)}; item []list2 = { new item( "milk" , 20), new item( "bread" , 15), new item( "wheat" , 40), new item( "apple" , 60)}; int m = list1.Length; int n = list2.Length; Console.Write( "Count = " + countItems(list1, m, list2, n)); } } // This code is contributed by PrinciRaj1992

输出如下:
Count = 2

时间复杂度:O(m * n)。
辅助空间:O(1)。
方法2(二分搜索):
排序
list2
按项目名称的字母顺序排列。现在, 对于
列表1
检查它是否存在
list2
使用二进制搜索技术并从中获取价格
list2
。如果价格不同, 则增加
计数
.
CPP
// C++ implementation to count items common to both // the lists but with different prices #include < bits/stdc++.h> using namespace std; // details of an item struct item { string name; int price; }; // comparator function used for sorting bool compare( struct item a, struct item b) { return (a.name.compare(b.name) < = 0); } // function to search 'str' in 'list2[]'. If it exists then // price associated with 'str' in 'list2[]' is being // returned else -1 is returned. Here binary serach // trechnique is being applied for searching int binary_search(item list2[], int low, int high, string str) { while (low < = high) { int mid = (low + high) / 2; // if true the item 'str' is in '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; }// item 'str' is not in 'list2' return -1; } // function to count items common to both // the lists but with different prices int countItems(item list1[], int m, item list2[], int n) { // sort 'list2' in alphabetcal order of // items name sort(list2, list2 + n, compare); // initial count int count = 0; for ( int i = 0; i < m; i++) { // get the price of item 'list1[i]' from 'list2' // if item in not present in second list then // -1 is being obtained int r = binary_search(list2, 0, n-1, list1[i].name); // if item is present in list2 with a // different price if ((r != -1) & & (r != list1[i].price)) count++; }// required count of items return count; } // Driver program to test above 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(有效方法):
使用创建哈希表
(核心价值)
元组为
(商品名称, 价格)
。插入的元素
列表1
在哈希表中。现在, 对于
list2
检查它是否是哈希表。如果存在, 则检查其价格是否与哈希表中的值不同。如果是这样, 则增加
计数
.
C ++
// C++ implementation to count items common to both // the lists but with different prices #include < bits/stdc++.h> using namespace std; // details of an item struct item { string name; int price; }; // function to count items common to both // the lists but with different prices int countItems(item list1[], int m, item list2[], int n) { // 'um' implemented as hash table that contains // item name as the key and price as the value // associated with the key unordered_map< string, int > um; int count = 0; // insert elements of 'list1' in 'um' for ( int i = 0; i < m; i++) um[list1[i].name] = list1[i].price; // for each element of 'list2' check if it is // present in 'um' with a different price // value for ( int i = 0; i < n; i++) if ((um.find(list2[i].name) != um.end()) & & (um[list2[i].name] != list2[i].price)) count++; // required count of items return count; } // Driver program to test above 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; }

Java
// Java implementation to count // items common to both the lists // but with different prices import java.util.*; class GFG{ // details of an item static class item { String name; int price; public item(String name, int price) { this .name = name; this .price = price; } }; // function to count items common to both // the lists but with different prices static int countItems(item list1[], int m, item list2[], int n) { // 'um' implemented as hash table that contains // item name as the key and price as the value // associated with the key HashMap< String, Integer> um = new HashMap< > (); int count = 0 ; // insert elements of 'list1' in 'um' for ( int i = 0 ; i < m; i++) um.put(list1[i].name, list1[i].price); // for each element of 'list2' check if it is // present in 'um' with a different price // value for ( int i = 0 ; i < n; i++) if ((um.containsKey(list2[i].name)) & & (um.get(list2[i].name) != list2[i].price)) count++; // required count of items return count; } // Driver program to test above public static void main(String[] args) { item list1[] = { new item( "apple" , 60 ), new item( "bread" , 20 ), new item( "wheat" , 50 ), new item( "oil" , 30 )}; item list2[] = { new item( "milk" , 20 ), new item( "bread" , 15 ), new item( "wheat" , 40 ), new item( "apple" , 60 )}; int m = list1.length; int n = list2.length; System.out.print( "Count = " + countItems(list1, m, clist2, n)); } } // This code is contributed by gauravrajput1

C#
// C# implementation to count // items common to both the lists // but with different prices using System; using System.Collections.Generic; class GFG{ // Details of an item public class item { public String name; public int price; public item(String name, int price) { this .name = name; this .price = price; } }; // Function to count items common to // both the lists but with different prices static int countItems(item []list1, int m, item []list2, int n) { // 'um' implemented as hash table // that contains item name as the // key and price as the value // associated with the key Dictionary< String, int > um = new Dictionary< String, int > (); int count = 0; // Insert elements of 'list1' // in 'um' for ( int i = 0; i < m; i++) um.Add(list1[i].name, list1[i].price); // For each element of 'list2' // check if it is present in // 'um' with a different price // value for ( int i = 0; i < n; i++) if ((um.ContainsKey(list2[i].name)) & & (um[list2[i].name] != list2[i].price)) count++; // Required count of items return count; } // Driver code public static void Main(String[] args) { item []list1 = { new item( "apple" , 60), new item( "bread" , 20), new item( "wheat" , 50), new item( "oil" , 30)}; item []list2 = { new item( "milk" , 20), new item( "bread" , 15), new item( "wheat" , 40), new item( "apple" , 60)}; int m = list1.Length; int n = list2.Length; Console.Write( "Count = " + countItems(list1, m, list2, n)); } } // This code is contributed by shikhasingrajput

输出如下:
Count = 2

时间复杂度:O(m + n)。
辅助空间:O(m)。
为了提高效率, 应在哈希表中插入元素数量最少的列表。

    推荐阅读