相关疑难解决方法(0)

这是一个家庭作业问题.他们说,这需要O(logN + logM)地方N和M是数组的长度.

让我们命名的数组a和b.显然我们可以忽略所有a[i]和b[i]i> k.
首先,让我们来比较一下a[k/2]和b[k/2].让b[k/2]> a[k/2].因此我们也可以丢弃所有b[i],其中i> k/2.

现在我们拥有所有a[i],我<k和所有b[i],其中我<k/2找到答案.

你下一步怎么做？

我需要找到k两个排序数组中的最大元素,但有一个扭曲.

该算法假定k<=max(m,n)和索引出错时k>max(m,n).在我的问题我知道,总是会k>(m+n)/2,因此k>min(m,n),所以我需要改变儒勒Olléon的回答有点......我只是不明白这一点:〜

我已经找到了这个链接第3页,但是那里有bug(当实现时,它没有返回正确的答案)

我知道快速解决方法是将两个数组乘以-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; …