Ram和Shyam想选择一个网站来学习编程，他们都有一个用字符串表示的最喜欢的网站列表。 你需要用最少的索引和帮助他们找到共同的兴趣。如果答案之间存在选择关系，请打印所有答案，无需排序。假设总是有答案的。
null
例如：
Input : ["GeeksforGeeks", "Udemy", "Coursera", "edX"] ["Codecademy", "Khan Academy", "GeeksforGeeks"]Output : "GeeksforGeeks"Explanation : GeeksforGeeks is the only common website in two listsInput : ["Udemy", "GeeksforGeeks", "Coursera", "edX"] ["GeeksforGeeks", "Udemy", "Khan Academy", "Udacity"]Output : "GeeksforGeeks" "Udemy"Explanation : There are two common websites and index sum of both is same.
天真的方法：
其想法是尝试从0到大小之和的所有索引和。对于每个和，检查是否有具有给定和的对。一旦我们找到一对或多对，我们就打印出来并返回。
C++
#include <bits/stdc++.h> using namespace std; // Function to print common strings with minimum index sum void find(vector<string> list1, vector<string> list2) { vector<string> res; // resultant list int max_possible_sum = list1.size() + list2.size() - 2; // iterating over sum in ascending order for ( int sum = 0; sum <= max_possible_sum ; sum++) { // iterating over one list and check index // (Corresponding to given sum) in other list for ( int i = 0; i <= sum; i++) // put common strings in resultant list if (i < list1.size() && (sum - i) < list2.size() && list1[i] == list2[sum - i]) res.push_back(list1[i]); // if common string found then break as we are // considering index sums in increasing order. if (res.size() > 0) break ; } // print the resultant list for ( int i = 0; i < res.size(); i++) cout << res[i] << " " ; } // Driver code int main() { // Creating list1 vector<string> list1; list1.push_back( "GeeksforGeeks" ); list1.push_back( "Udemy" ); list1.push_back( "Coursera" ); list1.push_back( "edX" ); // Creating list2 vector<string> list2; list2.push_back( "Codecademy" ); list2.push_back( "Khan Academy" ); list2.push_back( "GeeksforGeeks" ); find(list1, list2); return 0; } |
JAVA
import java.util.*; class GFG { // Function to print common Strings with minimum index sum static void find(Vector<String> list1, Vector<String> list2) { Vector<String> res = new Vector<>(); // resultant list int max_possible_sum = list1.size() + list2.size() - 2 ; // iterating over sum in ascending order for ( int sum = 0 ; sum <= max_possible_sum ; sum++) { // iterating over one list and check index // (Corresponding to given sum) in other list for ( int i = 0 ; i <= sum; i++) // put common Strings in resultant list if (i < list1.size() && (sum - i) < list2.size() && list1.get(i) == list2.get(sum - i)) res.add(list1.get(i)); // if common String found then break as we are // considering index sums in increasing order. if (res.size() > 0 ) break ; } // print the resultant list for ( int i = 0 ; i < res.size(); i++) System.out.print(res.get(i)+ " " ); } // Driver code public static void main(String[] args) { // Creating list1 Vector<String> list1 = new Vector<>(); list1.add( "GeeksforGeeks" ); list1.add( "Udemy" ); list1.add( "Coursera" ); list1.add( "edX" ); // Creating list2 Vector<String> list2= new Vector<>(); list2.add( "Codecademy" ); list2.add( "Khan Academy" ); list2.add( "GeeksforGeeks" ); find(list1, list2); } } // This code contributed by Rajput-Ji |
Python3
# Function to print common strings # with minimum index sum def find(list1, list2): res = [] # resultant list max_possible_sum = len (list1) + len (list2) - 2 # iterating over sum in ascending order for sum in range (max_possible_sum + 1 ): # iterating over one list and check index # (Corresponding to given sum) in other list for i in range ( sum + 1 ): # put common strings in resultant list if (i < len (list1) and ( sum - i) < len (list2) and list1[i] = = list2[ sum - i]): res.append(list1[i]) # if common string found then break as we are # considering index sums in increasing order. if ( len (res) > 0 ): break # print the resultant list for i in range ( len (res)): print (res[i], end = " " ) # Driver code # Creating list1 list1 = [] list1.append( "GeeksforGeeks" ) list1.append( "Udemy" ) list1.append( "Coursera" ) list1.append( "edX" ) # Creating list2 list2 = [] list2.append( "Codecademy" ) list2.append( "Khan Academy" ) list2.append( "GeeksforGeeks" ) find(list1, list2) # This code is contributed by Mohit Kumar |
C#
using System; using System.Collections.Generic; class GFG { // Function to print common Strings with minimum index sum static void find(List<String> list1, List<String> list2) { List<String> res = new List<String>(); // resultant list int max_possible_sum = list1.Count + list2.Count - 2; // iterating over sum in ascending order for ( int sum = 0; sum <= max_possible_sum ; sum++) { // iterating over one list and check index // (Corresponding to given sum) in other list for ( int i = 0; i <= sum; i++) // put common Strings in resultant list if (i < list1.Count && (sum - i) < list2.Count && list1[i] == list2[sum - i]) res.Add(list1[i]); // if common String found then break as we are // considering index sums in increasing order. if (res.Count > 0) break ; } // print the resultant list for ( int i = 0; i < res.Count; i++) Console.Write(res[i]+ " " ); } // Driver code public static void Main(String[] args) { // Creating list1 List<String> list1 = new List<String>(); list1.Add( "GeeksforGeeks" ); list1.Add( "Udemy" ); list1.Add( "Coursera" ); list1.Add( "edX" ); // Creating list2 List<String> list2= new List<String>(); list2.Add( "Codecademy" ); list2.Add( "Khan Academy" ); list2.Add( "GeeksforGeeks" ); find(list1, list2); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Function to print common Strings with minimum index sum function find(list1, list2) { let res = []; // resultant list let max_possible_sum = list1.length + list2.length - 2; // iterating over sum in ascending order for (let sum = 0; sum <= max_possible_sum ; sum++) { // iterating over one list and check index // (Corresponding to given sum) in other list for (let i = 0; i <= sum; i++) // put common Strings in resultant list if (i < list1.length && (sum - i) < list2.length && list1[i] == list2[sum - i]) res.push(list1[i]); // if common String found then break as we are // considering index sums in increasing order. if (res.length > 0) break ; } // print the resultant list for (let i = 0; i < res.length; i++) document.write(res[i]+ " " ); } // Creating list1 let list1 = []; list1.push( "GeeksforGeeks" ); list1.push( "Udemy" ); list1.push( "Coursera" ); list1.push( "edX" ); // Creating list2 let list2= []; list2.push( "Codecademy" ); list2.push( "Khan Academy" ); list2.push( "GeeksforGeeks" ); find(list1, list2); // This code is contributed by mukesh07. </script> |
输出：
GeeksforGeeks
时间复杂性： O（（l） 1. +l 2. ) 2. *x） ，我在哪里 1. 我呢 2. 分别是列表1和列表2的长度，x表示字符串长度。 辅助空间： O（l*x），其中x表示结果列表的长度，l表示最大字数的长度。
使用哈希：
- 遍历列表1，为哈希表中列表1的每个元素创建一个索引项。
- 遍历list2，对于每个元素，检查同一元素是否已经作为键存在于映射中。如果是，这意味着两个列表中都存在该元素。
- 找出两个列表中公共元素对应的索引之和。如果该总和小于目前为止获得的最小总和，则更新结果列表。
- 如果总和等于迄今为止获得的最小总和，则在结果列表中添加一个与列表2中的元素对应的额外条目。
C++
// Hashing based C++ program to find common elements // with minimum index sum. #include <bits/stdc++.h> using namespace std; // Function to print common strings with minimum index sum void find(vector<string> list1, vector<string> list2) { // mapping strings to their indices unordered_map<string, int > map; for ( int i = 0; i < list1.size(); i++) map[list1[i]] = i; vector<string> res; // resultant list int minsum = INT_MAX; for ( int j = 0; j < list2.size(); j++) { if (map.count(list2[j])) { // If current sum is smaller than minsum int sum = j + map[list2[j]]; if (sum < minsum) { minsum = sum; res.clear(); res.push_back(list2[j]); } // if index sum is same then put this // string in resultant list as well else if (sum == minsum) res.push_back(list2[j]); } } // Print result for ( int i = 0; i < res.size(); i++) cout << res[i] << " " ; } // Driver code int main() { // Creating list1 vector<string> list1; list1.push_back( "GeeksforGeeks" ); list1.push_back( "Udemy" ); list1.push_back( "Coursera" ); list1.push_back( "edX" ); // Creating list2 vector<string> list2; list2.push_back( "Codecademy" ); list2.push_back( "Khan Academy" ); list2.push_back( "GeeksforGeeks" ); find(list1, list2); return 0; } |
JAVA
// Hashing based Java program to find common elements // with minimum index sum. import java.util.*; class GFG { // Function to print common Strings with minimum index sum static void find(Vector<String> list1, Vector<String> list2) { // mapping Strings to their indices Map<String, Integer> map = new HashMap<>(); for ( int i = 0 ; i < list1.size(); i++) map.put(list1.get(i), i); Vector<String> res = new Vector<String>(); // resultant list int minsum = Integer.MAX_VALUE; for ( int j = 0 ; j < list2.size(); j++) { if (map.containsKey(list2.get(j))) { // If current sum is smaller than minsum int sum = j + map.get(list2.get(j)); if (sum < minsum) { minsum = sum; res.clear(); res.add(list2.get(j)); } // if index sum is same then put this // String in resultant list as well else if (sum == minsum) res.add(list2.get(j)); } } // Print result for ( int i = 0 ; i < res.size(); i++) System.out.print(res.get(i) + " " ); } // Driver code public static void main(String[] args) { // Creating list1 Vector<String> list1 = new Vector<String>(); list1.add( "GeeksforGeeks" ); list1.add( "Udemy" ); list1.add( "Coursera" ); list1.add( "edX" ); // Creating list2 Vector<String> list2 = new Vector<String>(); list2.add( "Codecademy" ); list2.add( "Khan Academy" ); list2.add( "GeeksforGeeks" ); find(list1, list2); } } // This code is contributed by PrinciRaj1992 |
Python3
# Hashing based Python3 program to find # common elements with minimum index sum import sys # Function to print common strings # with minimum index sum def find(list1, list2): # Mapping strings to their indices Map = {} for i in range ( len (list1)): Map [list1[i]] = i # Resultant list res = [] minsum = sys.maxsize for j in range ( len (list2)): if list2[j] in Map : # If current sum is smaller # than minsum Sum = j + Map [list2[j]] if ( Sum < minsum): minsum = Sum res.clear() res.append(list2[j]) # If index sum is same then put this # string in resultant list as well elif ( Sum = = minsum): res.append(list2[j]) # Print result print ( * res, sep = " " ) # Driver code # Creating list1 list1 = [] list1.append( "GeeksforGeeks" ) list1.append( "Udemy" ) list1.append( "Coursera" ) list1.append( "edX" ) # Creating list2 list2 = [] list2.append( "Codecademy" ) list2.append( "Khan Academy" ) list2.append( "GeeksforGeeks" ) find(list1, list2) # This code is contributed by avanitrachhadiya2155 |
C#
// Hashing based C# program to find common elements // with minimum index sum. using System; using System.Collections.Generic; class GFG { // Function to print common Strings with minimum index sum static void find(List<String> list1, List<String> list2) { // mapping Strings to their indices Dictionary<String, int > map = new Dictionary<String, int >(); for ( int i = 0; i < list1.Count; i++) map.Add(list1[i], i); List<String> res = new List<String>(); // resultant list int minsum = int .MaxValue; for ( int j = 0; j < list2.Count; j++) { if (map.ContainsKey(list2[j])) { // If current sum is smaller than minsum int sum = j + map[list2[j]]; if (sum < minsum) { minsum = sum; res.Clear(); res.Add(list2[j]); } // if index sum is same then put this // String in resultant list as well else if (sum == minsum) res.Add(list2[j]); } } // Print result for ( int i = 0; i < res.Count; i++) Console.Write(res[i] + " " ); } // Driver code public static void Main(String[] args) { // Creating list1 List<String> list1 = new List<String>(); list1.Add( "GeeksforGeeks" ); list1.Add( "Udemy" ); list1.Add( "Coursera" ); list1.Add( "edX" ); // Creating list2 List<String> list2 = new List<String>(); list2.Add( "Codecademy" ); list2.Add( "Khan Academy" ); list2.Add( "GeeksforGeeks" ); find(list1, list2); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Hashing based Javascript program to // find common elements with minimum // index sum. // Function to print common Strings // with minimum index sum function find(list1, list2) { // Mapping Strings to their indices let map = new Map(); for (let i = 0; i < list1.length; i++) map.set(list1[i], i); // Resultant list let res = []; let minsum = Number.MAX_VALUE; for (let j = 0; j < list2.length; j++) { if (map.has(list2[j])) { // If current sum is smaller than minsum let sum = j + map.get(list2[j]); if (sum < minsum) { minsum = sum; res = []; res.push(list2[j]); } // If index sum is same then put this // String in resultant list as well else if (sum == minsum) res.push(list2[j]); } } // Print result for (let i = 0; i < res.length; i++) document.write(res[i] + " " ); } // Driver code // Creating list1 let list1 = []; list1.push( "GeeksforGeeks" ); list1.push( "Udemy" ); list1.push( "Coursera" ); list1.push( "edX" ); // Creating list2 let list2 = []; list2.push( "Codecademy" ); list2.push( "Khan Academy" ); list2.push( "GeeksforGeeks" ); find(list1, list2); // This code is contributed by rameshtravel07 </script> |
输出：
GeeksforGeeks
时间复杂性： O（l） 1. +l 2. )，我在哪里 1. 我呢 2. 分别是列表1和列表2的长度。 辅助空间： O（l） 1. *x） ，其中x表示结果列表的长度，l表示最大字数的长度。
本文由 阿卡什·帕尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
