2

我需要k在两个排序的数组中找到最大的元素，但要有所不同。

该算法假设k<=max(m,n)当 时索引出错k>max(m,n)。在我的问题中，我知道这将永远存在k>(m+n)/2，因此k>min(m,n)我需要稍微改变 Jules Olléon 的答案......我只是看不出是哪一点:~

我找到了这个链接第 3 页，但是那里有错误（实施时，它不会返回正确的答案）

我知道一个快速的解决方法是将两个数组都乘以 -1 并取该联合中最小的 k 并将答案乘以 -1 但这会使代码不可读。

这不是家庭作业。

好的，我想我误解了尼尔的回答或其他东西，因为这就是我给“他”的东西

#include <algorithm>
#include <fstream>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <vector>

#include <Eigen/Dense>
using namespace Eigen;
using Eigen::VectorXf;
using Eigen::VectorXi;

float getNth(VectorXf& v1,VectorXf& v2,int& n){
        int step=(n/4),i1=(n/2),i2=(n-i1);
        while(!(v2(i2)>=v1(i1-1) && v1(i1)>v2(i2-1))){                   
            if(v1(i1-1)>=v2(i2-1)){
                i1-=step;
                i2+=step;
            } else {
                i1+=step;
                i2-=step;
            }
            step/=2;
            if(!step) step=1;
        }
        if(v1(i1-1)>=v2(i2-1))
            return v1(i1-1);
            else
            return v2(i2-1);    
}
int main(){  
    int p,q,n,k,l;
    float sol;
    std:: cout << "enter p " << std::endl;
    std::cin >> p; 
    std:: cout << "enter q " << std::endl;
    std::cin >> q;
    n=p+q;
    std:: cout  << " enter k larger than " << std::min(p,q) << " and smaller than " << n-1 << std::endl;
    std::cin >> k;
    
    k=n-k-1;
    
    srand(time(NULL));
    VectorXf v1=VectorXf::Random(p);
    srand(time(NULL));
    VectorXf v2=VectorXf::Random(q);
    VectorXf v3(n);
    v3 << v1, v2;
    std::sort(v3.data(),v3.data()+v3.size(),std::greater<float>()); //std::greater<float>()
    std::sort(v1.data(),v1.data()+v1.size(),std::greater<float>());
    std::sort(v2.data(),v2.data()+v2.size(),std::greater<float>());
    
    sol=getNth(v1,v2,k);
    std::cout << sol << std::endl;
    std::cout << v3(k) <<   std::endl;
    return 0;  
}

这就是我得到的：

enter p 
12
enter q 
32
 enter k larger than 12 and smaller than 43
13
nthoftwo: /Desktop/work/p1/geqw4/vi3/out/sp/ccode/eigen/Eigen/src/Core/DenseCoeffsBase.h:409: Eigen::DenseCoeffsBase<Derived, 1>::Scalar& Eigen::DenseCoeffsBase<Derived, 1>::operator()(Eigen::DenseCoeffsBase<Derived, 1>::Index) [with Derived = Eigen::Matrix<float, -0x00000000000000001, 1>, Eigen::DenseCoeffsBase<Derived, 1>::Scalar = float, Eigen::DenseCoeffsBase<Derived, 1>::Index = long int]: Assertion `index >= 0 && index < size()' failed.
Aborted (core dumped)

如果您不熟悉 eigen：该错误是由以下原因引起的索引越界错误getNth(v1,v2,k)

编辑：

这是对下面 JF Sebastian 简单而优雅的解决方案的一个非常小的修改——所有错误都是我的，但它似乎有效。目的是使用原始索引（即我不确定 Neil 的想法是否不可或缺）。

#include <algorithm>
#include <fstream>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <vector>
#include <cassert>
#include <iterator>

#include <Eigen/Dense>
using namespace Eigen;
using Eigen::VectorXf;
using Eigen::VectorXi;

template<class RandomIterator,class Compare>
typename std::iterator_traits<RandomIterator>::value_type
nsmallest(RandomIterator firsta,RandomIterator lasta,RandomIterator firstb,RandomIterator lastb,size_t n,Compare less) {
  assert(n<static_cast<size_t>((lasta-firsta)+(lastb-firstb)));
  if (firsta==lasta) return *(firstb+n);
  if (firstb==lastb) return *(firsta+n);

  size_t mida=(lasta-firsta)/2;
  size_t midb=(lastb-firstb)/2;
  if ((mida+midb)<n)
    return less(*(firstb+midb),*(firsta+mida))?
      nsmallest(firsta,lasta,firstb+midb+1,lastb,n-(midb+1),less):
      nsmallest(firsta+mida+1,lasta,firstb,lastb,n-(mida+1),less);
  else
    return less(*(firstb+midb),*(firsta+mida))?
      nsmallest(firsta,firsta+mida,firstb,lastb,n,less):
      nsmallest(firsta,lasta,firstb,firstb+midb,n,less);
}
int main(){  
    int p,q,n,k,l;
    float sol;
    std:: cout << "enter p " << std::endl;
    std::cin >> p; 
    std:: cout << "enter q " << std::endl;
    std::cin >> q;
    n=p+q;
    std:: cout  << " enter k larger than " << std::min(p,q) << " and smaller than " << n-1 << std::endl;
    std::cin >> k;
    
    srand(time(NULL));
    VectorXf v1=VectorXf::Random(p);
    srand(time(NULL));
    VectorXf v2=VectorXf::Random(q);
    VectorXf v3(n);
    v3 << v1, v2;
    std::sort(v3.data(),v3.data()+v3.size()); 
    std::sort(v1.data(),v1.data()+v1.size());
    std::sort(v2.data(),v2.data()+v2.size());
    
    sol=nsmallest(v1.data(),v1.data()+v1.size(),v2.data(),v2.data()+v2.size(),k,std::less<float>());
//if it works, these two should return the same.
    std::cout << sol << std::endl;  
    std::cout << v3(k) << std::endl;
    return 0;  
}
4

4 回答 4

6

从您的评论中，我了解到您希望找到给定 2 个逆向排序数组的第 k 个最小值，例如，fora={5,4,3}, b={2,1,0};和k=1预期结果是0，即最小值 - 第一个最小值（这意味着k从 开始计数1）。

给定nsmallest()适用于排序数组并接受自定义比较器的函数，您可以：

#include <functional> // greater<>
#include <iostream>

#define SIZE(a) (sizeof(a) / sizeof(*a))

int main() {
  int a[] = {5,4,3};
  int b[] = {2,1,0};
  int k = 1; // find minimum value, the 1st smallest value in a,b

  int i = k - 1; // convert to zero-based indexing
  int v = nsmallest(a, a + SIZE(a), b, b + SIZE(b),
            SIZE(a)+SIZE(b)-1-i, std::greater<int>());
  std::cout << v << std::endl; // -> 0
  return v;
}

我使用@Neil的建议来修复索引和@lambdapilgrim 对算法的回答：

#include <cassert>
#include <iterator>

template<class RandomIterator, class Compare>
typename std::iterator_traits<RandomIterator>::value_type
nsmallest(RandomIterator firsta, RandomIterator lasta,
          RandomIterator firstb, RandomIterator lastb,
          size_t n,
          Compare less) {
  assert(n < static_cast<size_t>((lasta - firsta) + (lastb - firstb)));
  if (firsta == lasta) return *(firstb + n);
  if (firstb == lastb) return *(firsta + n);

  size_t mida = (lasta - firsta) / 2;
  size_t midb = (lastb - firstb) / 2;
  if ((mida + midb) < n)
    return less(*(firstb + midb), *(firsta + mida)) ?
      nsmallest(firsta, lasta, firstb + midb + 1, lastb, n - (midb + 1), less) :
      nsmallest(firsta + mida + 1, lasta, firstb, lastb, n - (mida + 1), less);
  else
    return less(*(firstb + midb), *(firsta + mida)) ?
      nsmallest(firsta, firsta + mida, firstb, lastb, n, less) :
      nsmallest(firsta, lasta, firstb, firstb + midb, n, less);
}
于 2012-07-27T03:35:25.070 回答
4

th 最大的k元素也是m + n + 1 - kth* 最小的元素，因此您可以尝试以这种方式解决问题。

*从 1 开始计数。如果k是从 0 开始计数，请m + n - 1 - k改用。

于 2012-07-26T23:38:14.647 回答
0

我相信您想要类似于 mergesort 的合并步骤的东西，在该步骤中，您逐步比较 m 的第 i 个元素与 n 的第 j 个元素-但不是将值存储在数组中，您只是在寻找第 k 个最小的-所以当您找到它时，返回该值（和/或其索引）并退出该函数。

于 2012-07-26T23:29:46.383 回答
0

我不确定关于 k>max(m,n) 的交易是什么！

一个简单的解决方案：

def find(v1, start1, end1, v2, start2, end2, k):
    i = (start1+end1)/2
    j = binsearchrank(v2, start2, end2, v1[i])
    ranki = (i-start1+1) + (j-start2)
    if ranki > k:
        return find(v2, start2, j, v1, start1, i, k)
    elif ranki < k:
        return find(v2, j, end2, v1, i+1, end1, k-ranki)
    else:
        return v1[i]

复杂度为 O(log^2n)

于 2012-07-27T03:34:10.507 回答