Как эффективно найти ранг элемента в потоке чисел?

Недавно я пытаюсь найти медиану потока чисел со следующими условиями:

1. 3-х проходный алгоритм
2. O (nlog (n)) время
3. O (sqrt (n)) пространство

Ввод повторяется 3 раза, включая n, число целых чисел, за которыми следует n целых чисел a_i, так что:

1. n странно
2. 1≤n≤10 ^ 7
3. | A_i | ≤ 2 ^ {30}

Формат входных данных показан следующим образом:

5
1 3 4 2 5
5
1 3 4 2 5
5
1 3 4 2 5

Мой код пока показан следующим образом:

#ifdef STREAMING_JUDGE
#include "io.h"#define next_token io.next_token
#else
#include<string>
#include<iostream>
using namespace std;
string next_token()
{
string s;
cin >> s;
return s;
}
#endif

#include<cstdio>
#include<cstdlib>
#include<vector>
#include<algorithm>
#include<iostream>
#include<math.h>

using namespace std;

int main()
{
srand(time(NULL));
//1st pass: randomly choose sqrt(n) numbers from the given stream of numbers
int n = atoi(next_token().c_str());
int p = (int)ceil(sqrt(n));
vector<int> a;
for(int i=0; i<n; i++)
{
int s=atoi(next_token().c_str());
if( rand()%p == 0 && (int)a.size() < p )
{
a.push_back(s);
}
}
sort(a.begin(), a.end());
//2nd pass: find the k such that the median lies in a[k] and a[k+1], and find the rank of the median between a[k] and a[k+1]
next_token();
vector<int> rank(a.size(),0);
for( int j = 0; j < (int)a.size(); j++ )
{
rank.push_back(0);
}
for( int i = 0; i < n; i++ )
{
int s=atoi(next_token().c_str());
for( int j = 0; j < (int)rank.size(); j++ )
{
if( s<=a[j] )
{
rank[j]++;
}
}
}
int median = 0;
int middle = (n+1)/2;
int k;
if( (int)a.size() == 1 && rank.front() == middle )
{
median=a.front();
cout << median << endl;
return 0;
}
for( int j = 0; j < (int)rank.size(); j++ )
{
if( rank[j] == middle )
{
cout << rank[j] << endl;
return 0;
}
else if( rank[j] < middle && rank[j+1] > middle )
{
k = j;
break;
}
}
//3rd pass: sort the numbers in (a[k], a[k+1]) to find the median
next_token();
vector<int> FinalRun;
if( rank.empty() )
{
for(int i=0; i<n; i++)
{
a.push_back(atoi(next_token().c_str()));
}
sort(a.begin(), a.end());
cout << a[n>>1] << endl;
return 0;
}
else if( rank.front() > middle )
{
for( int i = 0; i < n; i++ )
{
int s = atoi(next_token().c_str());
if( s < a.front() )  FinalRun.push_back(s);
}
sort( FinalRun.begin(), FinalRun.end() );
cout << FinalRun[middle-1] << endl;
return 0;
}
else if ( rank.back() < middle )
{
for( int i = 0; i < n; i++ )
{
int s = atoi(next_token().c_str());
if( s > a.back() )  FinalRun.push_back(s);
}
sort( FinalRun.begin(), FinalRun.end() );
cout << FinalRun[middle-rank.back()-1] << endl;
return 0;
}
else
{
for( int i = 0; i < n; i++ )
{
int s = atoi(next_token().c_str());
if( s > a[k] && s < a[k+1] )  FinalRun.push_back(s);
}
sort( FinalRun.begin(), FinalRun.end() );
cout << FinalRun[middle-rank[k]-1] << endl;
return 0;
}
}

Но я все еще не могу достичь сложности времени O (nlogn).
Я предполагаю, что узкое место находится в части ранжирования (то есть, нахождение ранга медианы в (a [k], a [k + 1]) путем нахождения рангов выбранных a [i] во входном потоке номера.) во 2 проходе. Эта часть имеет O (nsqrt (n)) в моем коде.

Но я понятия не имею о том, как повысить эффективность рейтинга ……
Есть ли предложения по повышению эффективности? Заранее спасибо!

Дальнейшее объяснение «ранга»: ранг выборочного числа вычисляет количество чисел в потоке, меньшее или равное выбранному номеру. Например: во входных данных, приведенных выше, если выбраны числа a [0] = 2, a [1] = 4 и a [2] = 5, то rank [0] = 2, потому что есть два числа ( 1 и 2) в потоке, меньшем или равном [0].

Спасибо за всю твою помощь. Особенно предложение @ alexeykuzmin0 действительно может ускорить второй проход до времени O (n * logn). Но есть остающаяся проблема: в 1-ом проходе я выбираю числа с вероятностью 1 / sqrt (n). Когда не выбрано число (наихудший случай), вектор a пуст, что приводит к невозможности выполнения следующих проходов (т. Е. Происходит ошибка сегментации (дамп памяти)).
@Aconcagua, что означает «выбрать все оставшиеся элементы, если больше не требуется больше»? Благодарю.