比较数组元素时避免重复

问题是这样的：通过一个数组并找出加起来达到某个总和k的元素对。比较数组元素时避免重复

for (auto i : array) { 
    for (auto j : array) { 
     if (i+j==k) { 
      *Do something 
     } 
    } 
}

说我们有array = [1,2,5]和k=3; when i=1 and j=2，我们将执行做点什么。但是，当i=2和j=1，我们将执行再次做一些，即使我们已经找到了2个元素，我们将重复这个答案。

本质上，怎样才能通过一个数组，避免多次比较相同的2个元素？

来源

2015-09-09 John Smith

从排序向量开始...... – rici

-1

您可以将i + j的结果置于vector，然后sort it，然后remove duplicates，最后遍历该向量并“执行某些操作”。

来源

2015-09-09 01:16:33

排列array [i] + array [j]'的所有组合将比循环数组''慢很多。或者，你是否故意仅仅假设这是一个家庭作业问题的暗示，让OP考虑至少一个不好的方法来解决问题？ –

如果顺序没有关系，那么决定你想要的所有对中的哪一对：其中一个是i >= j，或者一个是i <= j。

for (i=0...) 
    for (j=i...)

像RICI评论的，这是一个非常缓慢（O(N^2)）算法相比分选（的拷贝）的载体。我认为你可以从头开始向前迭代i，并且从尾部向后迭代j，比较i+j <= k以决定是否修改i或接下来的j。

来源

2015-09-09 03:54:08

如果我是而不是让你的问题不对，那么这个解释过程可能是解决它的一种方法。

排序您在阵列增加为了（最好合并排序，因为它需要O（n.log（N））时间）。
现在，拿两个指标让叫他们低和高，其中低是索引到最左边的最小数量排序的阵列和高是索引到最右边的最大数相同的排序数组。

现在，这样做：

while(low < high) { 
    if(arr[low] + arr[high] == k) { 
     print "unique pair found" 
     high = high - 1; 
     low = low + 1; 
    } 

    else if(arr[low] + arr[high] > k){ 
     high = high - 1;  
    } 

    else { 
     low = low + 1; 
    } 
}

它的时间复杂度为O（n），它一定会让你在找什么？（任何疑问最受欢迎）。

来源

2015-09-10 09:02:38 surajsn

比较数组元素时避免重复

回答

相关问题