给定排序数组和参数k,找到大于或等于k的两个数之和的计数

Question

我试图在数组中找到总和等于k的所有对,解决方案需要O(n*log(n))时间.这是代码片段 -

  map<int,int> mymap;
  map<int,int>::iterator it;

  cin>>n>>k;

  for( int i = 0 ; i < n ; i++ ){

    cin>>a;

    if( mymap.find(a) != mymap.end() )
        mymap[a]++;
    else    
        mymap[a] = 1;

   }

   for( it = mymap.begin() ; it != mymap.end() ; it++ ){

    int val = it->first;

    if( mymap.find(k-val) != mymap.end() ){

        cnt += min( it->second, mymap.find(k-val)->second );
        it->second = 0;

    }

 }
  cout<<cnt;

我发现很难找到总和大于或等于k的所有对.我能想到的只是一个O(n ^ 2)解决方案.O(n ^ 2)可以是通过遍历数组找到所有对的强力方法.任何人都可以帮助我找到更好的解决方案,O(n)或O(nlgn)可能(如果存在)

Answer 1

另一种方法是在最佳情况下采用O(log n),在最坏情况下采用O(nlog n)进行正数可以这样做:

1. 在数组中查找等于k/2的元素,或者如果它不存在,则查找最小值大于k/2的元素.具有该元素和所有更大元素的所有组合将对我们感兴趣,因为当p> = k/2且s> = k/2时p + s> = k.对数组进行排序,因此可以使用带有一些修改的二进制搜索.此步骤将花费O(log n)时间.
2. 所有小于k/2 +元素的元素大于或等于"镜像元素"(根据中位数k/2)也会对我们感兴趣,因为当p = k/2-t和s时p + s> = k > = k/2 + t.在这里,我们需要循环通过小于k/2的元素并找到它们的镜像元素(二分搜索).如果镜像元素大于最后一个数组,则应该停止循环.

例如,我们有数组{1,3,5,8,11}和k = 10,所以在第一步我们将有k/2 = 5和对{5,7},{8,11},{8 ,11}.这些对的计数将通过公式l*(l-1)/ 2计算,其中l =元素的数量> = k/2.在我们的情况下,l = 3,所以count = 3*2/2 = 3.

在3号的第二步,镜像元素将是7(5-2 = 3和5 + 2 = 7),因此对{3,8}和{3,11}将感兴趣.对于1个数字镜子将是9(5-4 = 1和5 + 4 = 9),因此{1,11}是我们寻找的.

所以,如果k/2 <第一个数组元素,这个算法将是O(log n).

对于否定,算法会稍微复杂一些,但也可以用相同的复杂度来解决.

Answer 2

O(n)使用所谓的"两指针"或"两个迭代器"方法存在一种相当简单的方法.关键的想法是在同一个数组上运行两个迭代器(不一定是C++迭代器,索引也会这样做),这样如果第一个迭代器指向值x,那么第二个迭代器指向数组中的最小元素k-x.

我们将增加第一个迭代器,在执行此操作时,我们还将更改第二个迭代器以维护此属性.注意,随着第一个指针的增加,第二个指针的相应位置只会减小,所以在每次迭代时我们都可以从上一次迭代停止的位置开始; 我们永远不需要增加第二个指针.这就是我们实现O(n)时间的方式.

代码是这样的(没有测试这个,但想法应该清楚)

vector<int> a; // the given array
int r = a.size() - 1; 
for (int l=0; l<a.size(); l++) {
    while ((r >= 0) && (a[r] >= k - a[l]))
        r--;
    // now r is the maximal position in a so that a[r] < k - a[l]
    // so all elements right to r form a needed pair with a[l]
    ans += a.size() - r - 1; // this is how many pairs we have starting at l
}

另一种可能更简单的编码方法,但有点慢,是O(n log n)使用二进制搜索.对于a[l]数组的每个元素,您可以找到最大位置,r以便a[r]<k-a[l]使用二进制搜索(这r与第一个算法中的相同).