在没有嵌套循环的列表中查找重复项？

Question

我目前正在处理一项必须优化一些代码的作业。最慢的方法之一是在列表中查找重复元素的方法。场景中的重复项是这样工作的：假设您有一个元素列表，每个元素都有两个 ID，x 和 y。每个 x 值只能与一个 y 值配对，否则将其视为重复值，并且必须将原始值和重复值都添加到列表中。例如，元素列表是 (1,2) (1,2) (1,3) 在这种情况下，重复列表将包含 4 个元素，(1,2)(1,3) 和 (1, 2)( 1,3)，因为它们都具有相同的 x 值，但具有不同的 y 值。(1,2)(1,2) 不会被归类为重复项，因为 x 和 y 值相同。当前代码使用嵌套的 for 循环，它检查两个元素的 x 值是否相等但 y 值不同，但这很慢。在实际场景中，要素是供肾者与患者相匹配。所以每个捐赠者只能捐赠给一个病人。X 和 Y 是表示患者和捐赠者 ID 的字符串。如果有人知道这样做的更快方法，将不胜感激:)

Answer 1

你可以试试这个：

Map<Integer, Map<Integer, Long>> mmap = linkTable.stream()

      .collect(groupingBy(DonorsToPatientPair::getDonorID,

            groupingBy(DonorsToPatientPair::getPatientID, counting())));

变量 mmap 现在包含一个键映射到该键到频率的值映射。如果你想得到(d, p)的出现次数，你可以这样得到：

long freq = mmap.get(d).get(p)

为了处理地图，您可以使用如下代码：

for (int donor : mmap.keySet()) {

  Map<Integer, Long> patientMap = mmap.get(donor);

  if (patientMap.size() < 2) {

    continue; // no duplicates

  }

  // *** your code here ***

}

对于您自己的代码，您在循环中拥有捐赠者和从患者到其频率的地图。剩下的工作应该很容易完成。

Answer 2

您可以使用 x 值作为排序条件对数组进行排序。然后将数组切成具有相同 x 值的较小数组对。然后，您使用当前的算法仅在较小的块中本地查找重复项。虽然这仍然有嵌套循环，但它会执行得更快，因为搜索仅限于小数组，当 n 是元素数时，具有两个嵌套循环的搜索的复杂度为 O(n*n)。

Answer 3

我只是给你一个提示 把它当作一个图形问题并在 (u,v) 和之后绘制一条边，如果你发现一条指向 v 的边是重复的