计算两个列表中常见但价格不同的项目-yiteyi-C++库

给出两张清单 清单1 和 清单2 包含 M 和 N 项目分别。每个项目都与两个字段关联：名称和价格。问题是要计算两个清单中价格不同的物品。

null

例如：

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

资料来源： 认知面试经验|第5组。

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

方法1（天真的方法）： 使用两个嵌套循环比较 清单1 所有的物品 清单2 .如果发现匹配项的价格不同，则增加计数 .

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                       

Javascript

                         <script>                       
           
                         // Javascript 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                       
                         function                                     countItems(list1, m, list2, n)                       
                         {                       
                                                 var                                     count = 0;                       
                                   
                                                 // for each item of 'list1'                       
                                                 // check if it is in 'list2'                       
                                                 // but with a different price                       
                                                 for                                     (                                     var                                     i = 0; i < m; i++)                       
                                                 for                                     (                                     var                                     j = 0; j < n; j++)                       
           
                                                 if                                     (list1[i][0] === list2[j][0] &&                       
                                                 (list1[i][1] != list2[j][1]))                       
                                                 count++;                       
                                   
                                                 // required count of items                       
                                                 return                                     count;                       
                         }                       
           
                         // Driver program to test above                       
                         var                                     list1 = [[                                     "apple"                                     , 60], [                                     "bread"                                     , 20],                       
                                                 [                                     "wheat"                                     , 50], [                                     "oil"                                     , 30]];                       
                         var                                     list2 = [[                                     "milk"                                     , 20], [                                     "bread"                                     , 15],                       
                                                 [                                     "wheat"                                     , 40], [                                     "apple"                                     , 60]];                       
           
                         var                                     m = list1.length;                       
                         var                                     n = list2.length;                       
           
                         document.write(                                     "Count = "                                     + countItems(list1, m, list2, n));                       
                                   
           
                         </script>                       

输出：

Count = 2

时间复杂度：O（m*n）。辅助空间：O（1）。

方法2（二进制搜索）： 分类 清单2 按项目名称的字母顺序排列。现在，对于每一项 清单1 检查是否存在 清单2 使用二进制搜索技术，并从 清单2 .如果价格不同，则增加计数 .

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;                       
                         };                       
           
                         // 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                       
                         // search technique 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 alphabetical                       
                                                 // 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 code                       
                         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;                       
                                                 item(String name,                       
                                                 int                                     price)                       
                                                 {                       
                                                 this                                     .name = name;                       
                                                 this                                     .price = price;                       
                                                 }                       
                         };                       
           
                         // comparator function used for sorting                       
                         static                                     class                                     Com                                     implements                                     Comparator<item>                       
                         {                       
           
                                                 public                                     int                                     compare(item a,                       
                                                 item b)                       
                                                 {                       
                                                 return                                     a.name.compareTo(b.name);                       
                                                 }                       
           
                         }                       
           
                         // 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 search technique is being                       
                         // applied for searching                       
                         static                                     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.compareTo(str) ==                                     0                                     )                       
                                                 return                                     list2[mid].price;                       
                                                 else                                     if                                     (list2[mid].name.compareTo(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                       
                         static                                     int                                     countItems(item list1[],                                     int                                     m,                       
                                                 item list2[],                                     int                                     n)                       
                         {                       
                                                 // sort 'list2' in alphabetical                       
                                                 // order of items name                       
                                                 Arrays.sort(list2,                                     new                                     Com());                       
           
                                                 // 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 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                       

Javascript

                         <script>                       
                         // Javascript implementation to count                       
                         // items common to both the lists                       
                         // but with different prices                       
           
                         // Details of an item                       
                         class item                       
                         {                       
                                                 constructor(name,price)                       
                                                 {                       
                                                 this                                     .name = name;                       
                                                 this                                     .price = price;                       
                                                 }                       
                         }                       
           
                         // 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 search technique is being                       
                         // applied for searching                       
                         function                                     binary_search(list2,low,high,str)                       
                         {                       
                                                 while                                     (low <= high)                       
                                                 {                       
                                                 let mid = Math.floor((low + high) / 2);                       
                                   
                                                 // if true the item 'str' is in 'list2'                       
                                                 if                                     (list2[mid].name == (str))                       
                                                 return                                     list2[mid].price;                       
                                                 else                                     if                                     (list2[mid].name < (str))                       
                                                 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                       
                         function                                     countItems(list1, m, list2, n)                       
                         {                       
           
                                                 // sort 'list2' in alphabetical                       
                                                 // order of items name                       
                                                 list2.sort(                                     function                                     (a,b){                                     return                                     a.name==b.name;});                       
                                   
                                                 // initial count                       
                                                 let count = 0;                       
                                   
                                                 for                                     (let 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                       
                                                 let 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 code                       
                         let list1=[                                     new                                     item(                                     "apple"                                     , 60),                       
                                                 new                                     item(                                     "bread"                                     , 20),                       
                                                 new                                     item(                                     "wheat"                                     , 50),                       
                                                 new                                     item(                                     "oil"                                     , 30)];                       
                         let list2=[                                     new                                     item(                                     "milk"                                     , 20),                       
                                                 new                                     item(                                     "bread"                                     , 15),                       
                                                 new                                     item(                                     "wheat"                                     , 40),                       
                                                 new                                     item(                                     "apple"                                     , 60)];                       
                         let m = list1.length;                       
                         let n = list2.length;                       
                         document.write(                                     "Count = "                                     +                       
                                                 countItems(list1, m,                       
                                                 list2, n));                       
           
                         // This code is contributed by patel2127                       
                         </script>                       

输出：

Count = 2

时间复杂度：（m*log） _2. n）。辅助空间：O（1）。为了提高效率，应该对元素数最多的列表进行排序，并用于二进制搜索。

方法3（有效方法）： 使用创建哈希表 （关键，价值） 元组作为 （商品名称、价格） .插入 清单1 在哈希表中。现在，对于 清单2 检查它是否是哈希表。如果存在，则检查其价格是否与哈希表中的值不同。如果是这样，则增加计数 .

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                       

Javascript

                         <script>                       
           
                         // JavaScript implementation to count                       
                         // items common to both the lists                       
                         // but with different prices                       
           
                         // details of an item                       
                         class item                       
                         {                       
                                                 constructor(name,price)                       
                                                 {                       
                                                 this                                     .name = name;                       
                                                 this                                     .price = price;                       
                                                 }                       
                         }                       
           
                         // function to count items common to both                       
                         // the lists but with different prices                       
                         function                                     countItems(list1,m,list2,n)                       
                         {                       
                                                 // 'um' implemented as hash table that contains                       
                                                 // item name as the key and price as the value                       
                                                 // associated with the key                       
                                                 let um =                                     new                                     Map();                       
                                                 let count = 0;                       
                                   
                                                 // insert elements of 'list1' in 'um'                       
                                                 for                                     (let i = 0; i < m; i++)                       
                                                 um.set(list1[i].name, list1[i].price);                       
                                   
                                                 // for each element of 'list2' check if it is                       
                                                 // present in 'um' with a different price                       
                                                 // value                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 if                                     ((um.has(list2[i].name)) &&                       
                                                 (um.get(list2[i].name) != list2[i].price))                       
                                                 count++;                       
                                   
                                                 // required count of items                       
                                                 return                                     count;                       
                         }                       
           
                         // Driver program to test above                       
                         let list1=[                                     new                                     item(                                     "apple"                                     , 60),                       
                                                 new                                     item(                                     "bread"                                     , 20),                       
                                                 new                                     item(                                     "wheat"                                     , 50),                       
                                                 new                                     item(                                     "oil"                                     , 30)];                       
                         let list2=[                                     new                                     item(                                     "milk"                                     , 20),                       
                                                 new                                     item(                                     "bread"                                     , 15),                       
                                                 new                                     item(                                     "wheat"                                     , 40),                       
                                                 new                                     item(                                     "apple"                                     , 60)];                       
                         let m = list1.length;                       
                         let n = list2.length;                       
           
                         document.write(                                     "Count = "                                     +                       
                                                 countItems(list1, m,                       
                                                 list2, n));                       
           
           
                         // This code is contributed by unknown2108                       
           
                         </script>                       

输出：

Count = 2

时间复杂度：O（m+n）。辅助空间：O（m）。为了提高效率，应该在哈希表中插入元素数最少的列表。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章