问列表中的对
EN

Stack Overflow用户

提问于 2014-03-19 21:03:36

回答 3查看 91关注 0票数 2

在Java中查找列表中所有数字的唯一对的最佳方法是什么？我有一个解决方案，我将列表转换为数组，然后基本上将第一个元素与第二个元素配对，然后将第一个元素与第三个元素配对，依此类推。然而，结果是O(n^2)。下面是我的基本伪代码：

int arr[] = convertListToArray(arrList) 
   for i=1;i< arr.length; i++
     for j =1+1; j<arr.length; j++
          print arr[i] , arr[j]

这显然是o(n^2)。能不能用更好的方式做到这一点呢？

发布于 2014-03-19 21:08:07

在某些情况下，如果数字集受到约束，您可以使用一些技巧。从根本上说，您的问题是n^2，但是在一般情况下，您没有太多的选择。

如果您只需要唯一对，那么您可以从List中删除重复项(例如，将其转储到Set中，然后再次传回)，然后对其进行迭代。

然后对所有唯一对进行迭代：

for (int i=0;i<len;i++) {
    for (j=i+1;j<len;j++) {
    }
}

请注意，j从i+1开始循环，因此这比n^2的情况要好一些，尽管它仍然是非线性增长的。

票数 5

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/22506750

复制

相似问题

问列表中的对EN