0

因此，给定具有一系列数字的 n 个组（在给定的组中没有数字会重复。我如何搜索在 2 个或更多组中出现两次的数字。

例如：

答：1,2,3,4,5

B: 1,6,7,8,9

C:3.10,11,12

答案是：1 和 3，因为它们在三组中至少出现两次

我尝试将 x 组中的每个元素与组 Y 中的另一个元素进行比较，依此类推，但这效率不高，并且需要很长时间来计算更大的数据。

4

5 回答 5

5

确定一组项目是否包含重复元素的更有效方法之一是使用 HashSet。遍历所有元素并将它们添加到 HashSet，但在添加元素之前检查 HashSet 是否已包含该项目。如果该项目已经存在于 HashSet 中，则该项目已经存在于其他地方并且是重复的。

无需确保使用此方法对数据进行排序。对任何数据进行排序最多为 O(n lg n)。HashSet 方法只是 O(n)。

为了澄清评论中的混淆，这里是该算法的伪代码版本。

for Integer e in allLists {
    if (hashSet.contains(e)) {
        //e was added in a previous iteration of the loop and thus e is a duplicate
        results.add(e);
    } else {
        hashSet.add(e); 
    }
}
于 2013-08-12T15:37:23.573 回答
2

我会使用全局HashMap<Integer, Integer>来计算数组中出现的每个数字。

由于它被声明为，没有列表将包含重复元素，要找出两个或多个列表中的数字，只需遍历映射的键集并检查它们对应的counter.

复杂性：O(N)其中N是列表数组中的整数总数。

于 2013-08-12T15:41:34.383 回答
1

由于我不知道您的数据当前是如何存储的，因此我无法真正给您任何具体代码，但您可能想尝试以下步骤：

- 将每个列表中的所有值添加到一个主列表中。

- 对主列表进行排序。

- 遍历此列表，将多次出现的任何值添加到结果列表中。

编辑：由于您使用的是列表，因此您需要将每个字符串拆分为整数列表。你应该能够自己解决这个问题（至少试一试）。

于 2013-08-12T15:34:41.067 回答
0

如果数据已排序，如上所示，那么您可以对其进行相当多的优化。不要将每个列表的每个元素相互比较，而是将 A 中的元素与 B 中的元素进行比较，直到 B 中元素的值大于 A 中的值。这仅适用于您的数据已排序，如在您的问题。

于 2013-08-12T15:30:46.070 回答
0

您没有说明这些是如何存储的（例如在数组或链表中），或者数据是否始终按照此处所示的排序顺序排列，因此方法会有所不同。

假设您有一个排序值数组，我将遍历列表 A 中的每个元素并在列表 B 和 C 中进行二进制搜索。然后我将遍历列表 B 中的所有元素并在列表 C 中进行二进制搜索. 如果数据未排序，则应先使用排序算法对其进行排序（尽管我认为 Arrays 类有一个内置的排序方法可以使用）

于 2013-08-12T15:31:34.443 回答