找到包含整数的 n 个链表中的公共元素,并返回该列表。

huangapple go评论68阅读模式
英文:

Given n linked list containing integers, find the common elements between them and return the list

问题

我在最近的面试中被问到了这个问题。在规定的时间内,我无法想出一个令人满意的答案。

给定 N 个包含整数的单链表,找出它们之间的公共元素或交点,并返回仅包含公共元素的链表。

示例:

输入:

list1 = [1, 3, 4, 5, 10, 3]

list2 = [1, 2, 4, 8, 7, 2]

list3 = [9, 11, 1, 4]

输出:

list = [1, 4]

注意: 请注意,同一链表中的重复元素不应予考虑。

英文:

I was asked this question in one of my recent interviews. I could not come up with a satisfactory answer within the given time.

Given N singly-linked lists containing integers, find the common elements or intersection points between them and return the list containing only the common elements.

Example:

Input:

list1 = [1, 3, 4, 5, 10, 3]

list2 = [1, 2, 4, 8, 7, 2]

list3 = [9, 11, 1, 4]

Output:

list = [1, 4]

Note: Please note that duplicate elements within the same list shall not be considered.

答案1

得分: 1

如果列表实现了集合框架的通用List接口,可以使用retainAll方法实现:

List<Integer> list1 = Arrays.asList(1, 3, 4, 5, 10, 3);
List<Integer> list2 = Arrays.asList(1, 2, 4, 8, 7, 2);
List<Integer> list3 = Arrays.asList(9, 11, 1, 4);

List<Integer> result = new ArrayList<>(list1);

Stream.of(list2, list3).forEach(result::retainAll);
System.out.println(result);

输出:

[1, 4]
英文:

If the lists implement common List interface of the Collections framework, it can be implemented using retainAll method:

List&lt;Integer&gt; list1 = Arrays.asList(1, 3, 4, 5, 10, 3);
List&lt;Integer&gt; list2 = Arrays.asList(1, 2, 4, 8, 7, 2);
List&lt;Integer&gt; list3 = Arrays.asList(9, 11, 1, 4);
	    
List&lt;Integer&gt; result = new ArrayList&lt;&gt;(list1);

Stream.of(list2, list3).forEach(result::retainAll);
System.out.println(result);

Output:

[1, 4]

答案2

得分: 0

步骤 1: 维护一个名为 HashMap<Integer, Integer> List_Frequency 的哈希映射,用于存储包含该元素的列表的频率。

步骤 2: 遍历每个列表。在再次遍历时,维护另一个名为 HashMap<Integer, Integer> Visit 的哈希映射,以了解您是否首次访问列表中的元素。这样,它将只导致 HashMap List_Frequency 增加一次。

步骤 3: 遍历哈希映射 List_Frequency 以了解哪些元素被访问了 N 次。

英文:

Step 1: Maintain a HashMap<Integer, Integer> List_Frequency for storing frequency of lists in which that element is present.

Step 2: Traverse each list. While traversing again maintain another HashMap<Integer, Integer> Visit to know that you are visiting an element in the list for the first time or not. So, that it leads to increment the HashMap List_Frequency only once.

Step 3: Traverse the HashMap List_Frequency to know which elements are visited N times.

huangapple
  • 本文由 发表于 2020年8月9日 20:21:13
  • 转载请务必保留本文链接:https://go.coder-hub.com/63326294.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定