找到数组中满足ab=cd的所有对（a，b）和（c，d）-yiteyi-C++库

给定一个不同的整数数组，任务是找到两对（a，b）和（c，d），这样ab=cd，其中a，b，c和d是不同的元素。 例如：

null

Input  : arr[] = {3, 4, 7, 1, 2, 9, 8}Output : 4 2 and 1 8Product of 4 and 2 is 8 and also product of 1 and 8 is 8 .Input  : arr[] = {1, 6, 3, 9, 2, 10};Output : 6 3 and 9 2

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

A. 简单解决方案 就是运行四个循环来生成所有可能的四倍数组元素。对于每四个（a，b，c，d），检查a*b=c*d。此解决方案的时间复杂度为O（n ^4. ). 一 有效解决方案 这个问题的关键是使用哈希。在哈希表中，我们使用乘积作为密钥，使用对作为值。

1. For i=0 to n-12.   For j=i+1 to n-1       a) Find  prod = arr[i]*arr[j]              b) If prod is not available in hash then make             H[prod] = make_pair(i, j) // H is hash table       c) If product is also available in hash           then print previous and current elements          of array

C++

                         // C++ program to find four elements a, b, c                       
                         // and d in array such that ab = cd                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to find out four elements in array                       
                         // whose product is ab = cd                       
                         void                                     findPairs(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 bool                                     found =                                     false                                     ;                       
                                                 unordered_map<                                     int                                     , pair <                                     int                                     ,                                     int                                     > > H;                       
                                                 for                                     (                                     int                                     i=0; i<n; i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j=i+1; j<n; j++)                       
                                                 {                       
                                                 // If product of pair is not in hash table,                       
                                                 // then store it                       
                                                 int                                     prod = arr[i]*arr[j];                       
                                                 if                                     (H.find(prod) == H.end())                       
                                                 H[prod] = make_pair(i,j);                       
           
                                                 // If product of pair is also available in                       
                                                 // then print current and previous pair                       
                                                 else                       
                                                 {                       
                                                 pair<                                     int                                     ,                                     int                                     > pp = H[prod];                       
                                                 cout << arr[pp.first] <<                                     " "                                     << arr[pp.second]                       
                                                 <<                                     " and "                                     << arr[i]<<                                     " "                                     <<arr[j]<<endl;                       
                                                 found =                                     true                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 // If no pair find then print not found                       
                                                 if                                     (found ==                                     false                                     )                       
                                                 cout <<                                     "No pairs Found"                                     << endl;                       
                         }                       
           
                         //Driven code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {1, 2, 3, 4, 5, 6, 7, 8};                       
                                                 int                                     n =                                     sizeof                                     (arr)/                                     sizeof                                     (                                     int                                     );                       
                                                 findPairs(arr, n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find four elements a, b, c                       
                         // and d in array such that ab = cd                       
                         import                                     java.io.*;                       
                         import                                     java.util.*;                       
           
                         class                                     GFG {                       
                                   
                                                 public                                     static                                     class                                     pair {                       
                                   
                                                 int                                     first,second;                       
                                   
                                                 pair(                                     int                                     f,                                     int                                     s)                       
                                                 {                       
                                                 first = f;                       
                                                 second = s;                       
                                                 }                       
                                                 };                       
                                   
                                                 // Function to find out four elements                       
                                                 // in array whose product is ab = cd                       
                                                 public                                     static                                     void                                     findPairs(                                     int                                     arr[],                                     int                                     n)                       
                                                 {                       
                                   
                                                 boolean                                     found =                                     false                                     ;                       
                                                 HashMap<Integer, pair> hp =                       
                                                 new                                     HashMap<Integer, pair>();                       
                                   
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j = i +                                     1                                     ; j < n; j++)                       
                                                 {                       
                                   
                                                 // If product of pair is not in                       
                                                 // hash table, then store it                       
                                                 int                                     prod = arr[i] * arr[j];                       
                                   
                                                 if                                     (!hp.containsKey(prod))                       
                                                 hp.put(prod,                                     new                                     pair(i,j));                       
                                   
                                                 // If product of pair is also                       
                                                 // available in then print                       
                                                 // current and previous pair                       
                                                 else                       
                                                 {                       
                                                 pair p = hp.get(prod);                       
                                                 System.out.println(arr[p.first]                       
                                                 +                                     " "                                     + arr[p.second]                       
                                                 +                                     " "                                     +                                     "and"                                     +                                     " "                                     +                       
                                                 arr[i] +                                     " "                                     + arr[j]);                       
                                                 found =                                     true                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 // If no pair find then print not found                       
                                                 if                                     (found ==                                     false                                     )                       
                                                 System.out.println(                                     "No pairs Found"                                     );                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main (String[] args)                       
                                                 {                       
                                                 int                                     arr[] = {                                     1                                     ,                                     2                                     ,                                     3                                     ,                                     4                                     ,                                     5                                     ,                                     6                                     ,                                     7                                     ,                                     8                                     };                       
                                                 int                                     n = arr.length;                       
                                                 findPairs(arr, n);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by akash1295.                       

Python3

                         # Python3 program to find four elements                       
                         # a, b, c and d in array such that ab = cd                       
           
                         # Function to find out four elements in array                       
                         # whose product is ab = cd                       
                         def                                     findPairs(arr, n):                       
           
                                                 found                                     =                                     False                       
                                                 H                                     =                                     dict                                     ()                       
           
                                                 for                                     i                                     in                                     range                                     (n):                       
           
                                                 for                                     j                                     in                                     range                                     (i                                     +                                     1                                     , n):                       
                                   
                                                 # If product of pair is not in hash table,                       
                                                 # then store it                       
                                                 prod                                     =                                     arr[i]                                     *                                     arr[j]                       
           
                                                 if                                     (prod                                     not                                     in                                     H.keys()):                       
                                                 H[prod]                                     =                                     [i, j]                       
           
                                                 # If product of pair is also available in                       
                                                 # then prcurrent and previous pair                       
                                                 else                                     :                       
                                   
                                                 pp                                     =                                     H[prod]                       
                                                 print                                     (arr[pp[                                     0                                     ]], arr[pp[                                     1                                     ]],                       
                                                 "and"                                     , arr[i], arr[j])                       
                                                 found                                     =                                     True                       
                                   
                                                 # If no pair find then prnot found                       
                                                 if                                     (found                                     =                                     =                                     False                                     ):                       
                                                 print                                     (                                     "No pairs Found"                                     )                       
           
                         # Driver code                       
                         arr                                     =                                     [                                     1                                     ,                                     2                                     ,                                     3                                     ,                                     4                                     ,                                     5                                     ,                                     6                                     ,                                     7                                     ,                                     8                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                         findPairs(arr, n)                       
           
                         # This code is contributed                       
                         # by mohit kumar                       

C#

                         // C# program to find four elements a, b, c                       
                         // and d in array such that ab = cd                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
                         class                                     GFG                       
                         {                       
                                   
                                                 public                                     class                                     pair                       
                                                 {                       
                                   
                                                 public                                     int                                     first,second;                       
                                   
                                                 public                                     pair(                                     int                                     f,                                     int                                     s)                       
                                                 {                       
                                                 first = f;                       
                                                 second = s;                       
                                                 }                       
                                                 };                       
                                   
                                                 // Function to find out four elements                       
                                                 // in array whose product is ab = cd                       
                                                 public                                     static                                     void                                     findPairs(                                     int                                     [] arr,                                     int                                     n)                       
                                                 {                       
                                   
                                                 bool                                     found =                                     false                                     ;                       
                                                 Dictionary<                                     int                                     , pair> hp =                       
                                                 new                                     Dictionary<                                     int                                     , pair>();                       
                                   
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j = i + 1; j < n; j++)                       
                                                 {                       
                                   
                                                 // If product of pair is not in                       
                                                 // hash table, then store it                       
                                                 int                                     prod = arr[i] * arr[j];                       
                                   
                                                 if                                     (!hp.ContainsKey(prod))                       
                                                 hp.Add(prod,                                     new                                     pair(i,j));                       
                                   
                                                 // If product of pair is also                       
                                                 // available in then print                       
                                                 // current and previous pair                       
                                                 else                       
                                                 {                       
                                                 pair p = hp[prod];                       
                                                 Console.WriteLine(arr[p.first]                       
                                                 +                                     " "                                     + arr[p.second]                       
                                                 +                                     " "                                     +                                     "and"                                     +                                     " "                                     +                       
                                                 arr[i] +                                     " "                                     + arr[j]);                       
                                                 found =                                     true                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 // If no pair find then print not found                       
                                                 if                                     (found ==                                     false                                     )                       
                                                 Console.WriteLine(                                     "No pairs Found"                                     );                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main (String[] args)                       
                                                 {                       
                                                 int                                     []arr = {1, 2, 3, 4, 5, 6, 7, 8};                       
                                                 int                                     n = arr.Length;                       
                                                 findPairs(arr, n);                       
                                                 }                       
                         }                       
           
                         /* This code contributed by PrinciRaj1992 */                       

Javascript

                         <script>                       
                         // Javascript program to find four elements a, b, c                       
                         // and d in array such that ab = cd                       
                                   
                                                 // Function to find out four elements                       
                                                 // in array whose product is ab = cd                       
                                                 function                                     findPairs(arr,n)                       
                                                 {                       
                                                 let found =                                     false                                     ;                       
                                                 let  hp =                                     new                                     Map();                       
                                   
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 {                       
                                                 for                                     (let j = i + 1; j < n; j++)                       
                                                 {                       
                                   
                                                 // If product of pair is not in                       
                                                 // hash table, then store it                       
                                                 let prod = arr[i] * arr[j];                       
                                   
                                                 if                                     (!hp.has(prod))                       
                                                 hp.set(prod, [i,j]);                       
                                   
                                                 // If product of pair is also                       
                                                 // available in then print                       
                                                 // current and previous pair                       
                                                 else                       
                                                 {                       
                                                 let p = hp.get(prod);                       
                                                 document.write(arr[p[0]]                       
                                                 +                                     " "                                     + arr[p[1]]                       
                                                 +                                     " "                                     +                                     "and"                                     +                                     " "                                     +                       
                                                 arr[i] +                                     " "                                     + arr[j]+                                     "<br>"                                     );                       
                                                 found =                                     true                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 // If no pair find then print not found                       
                                                 if                                     (found ==                                     false                                     )                       
                                                 document.write(                                     "No pairs Found"                                     );                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 let arr=[1, 2, 3, 4, 5, 6, 7, 8];                       
                                                 let n = arr.length;                       
                                                 findPairs(arr, n);                       
                                   
           
                         // This code is contributed by unknown2108                       
                         </script>                       

输出：

1 6 and 2 31 8 and 2 42 6 and 3 43 8 and 4 6

时间复杂性： O（n） ^2. )假设哈希搜索和插入操作需要O（1）个时间。 相关文章： 在数组中找到四个元素a、b、c和d，使a+b=c+d 本文由 丹麦拉扎 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章