dart_kinselok
@dart_kinselok
Правильный вопрос содержит 50% искомого ответа...

Найти медиану двух отсортированных массивов?

Любопытная задачка вчера в руки попала. Даны два массива, заранее отсортированы по возрастанию, объемом в террабайт ( что подразумевает факт невозможности слияния их в один общий массив и повторной сортировки ). Требуется найти медиану (число, которое находится по серединке этих массивов, соедини мы их вместе. Например у массивов [1, 3, 5, 7] и [2, 6, 10] медиана будет 5, наглядно соедиинив, получим: [1, 2, 3, 5, 6, 7, 10], т.е., это не среднее арифметическое.), которая будет лежать по середке двух этих массивов, при чем отсортированных друг относительно друга. Ищу решения на С++, интересно было бы посмотреть на ваши идеи,ибо лично я, пока что, не допеp
______________________
Уже допер) Т.к. адекватных решений на CPP так и не увидел, но увидел пару великолепных идей и максимально их упростил, в ближайшее время накидаю решение на плюсах и зашвырну сюда. Всем ужасно благодарен!
  • Вопрос задан
  • 8620 просмотров
Решения вопроса 3
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
А в чём проблема? Длины массивов известны, берём полусумму длин и сдвигаемся параллельно по обоим массивам на эту величину, аналогично сортировке слиянием.
Ватиант на JS, то что с ходу получилось.
arr1 = [1, 3, 5, 7];
arr2 = [2, 6, 10];
p1 = arr1.length;
p2 = arr2.length;
n = p1+p2;
if (n == 0)
  n--;
med = 0;
p1--;
p2--;
while (0 < n) {
  if (p2 < 0 || (p1 >= 0 && arr1[p1] > arr2[p2]))
    med = arr1[p1--];
  else
    med = arr2[p2--];
  n -= 2;
}
if (0 == n) {
  if (p2 < 0 || (p1 >= 0 && arr1[p1] > arr2[p2]))
    med = med+arr1[p1];
  else
    med = med+arr2[p2];
  med /= 2;
}
console.log(med);


P.S. Если предварительно найти область пересечения массивов, то можно уменьшить объём просматриваемых данных.
Ответ написан
abyrkov
@abyrkov
JavaScripter
Что сложного?
var arr1 = [1, 3, 5, 7];
      arr2 = [2, 6, 10];
var counter1 = 0;
      counter2 = 0;
      counter3 = 0;
      counter4 = 0;
      counter5 = (arr1.length + arr2.length) / 2;
      endCounter = 0;
      totalCounter = 0;
for(; totalCounter < Math.round(counter5); totalCounter++){
counter4 = counter3;
if(arr1[counter1] <= arr2[counter2]) {
counter3 = arr1[counter1];
counter1++;
} else {
counter3 = arr2[counter2];
counter2++;
};
};
if(counter5 != Math.round(counter5)){
endCounter = (counter3 + counter4) / 2;
} else {
endCounter = counter3;
};
Ответ написан
dart_kinselok
@dart_kinselok Автор вопроса
Правильный вопрос содержит 50% искомого ответа...
Благодарен всем тем, кто помог, помогал, или пытался помочь. Из кучи решений собрал франкенштейна из разных кусков тел, и, в связке с полным условием, код выглядит следующим образом:

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

void bubble_sort(int *a, int array_size) {
	for (int i = 0; i < array_size - 1; i++) {
		for (int j = 0; j < array_size - i - 1; j++) {
			if (a[j] > a[j+1]) {
				int save;
				save = a[j];
				a[j] = a[j + 1];
				a[j + 1] = save;
			}
		}
	}
}

int main() {
	srand(time(0));

	int a_s;
	int b_s;
	int answer;

	cout << "Enter the size of the first array: ";
	cin >> a_s;
	cout << endl;
	cout << "Thx. Now, the second array: ";
	cin >> b_s;
	
	if (((a_s + b_s) % 2) == 0) {
		b_s = b_s + 1;
		cout << "First and second sizes are even. We'll add 1 point to size of second array. ";
	}

	cout << endl;
	cout << "===================================";
	cout << endl;

	cout << "Random values or input from keyboard? (1/2, yeap, i'm very lazy to use strcmp() :) ";
	cin >> answer;

	cout << "===================================";
	cout << endl;

	int *a = new int[a_s];
	int *b = new int[b_s];

	cout << "All values will be automatically sorted in ASC order!" << endl;
	cout << "Warning! Don't type the same numbres! The middle values also will be counted!!" << endl;
	cout << endl;

	if (answer == 1) {
		for (int i = 0; i < a_s; i++) {
			a[i] = rand() % 10 + 1;
		}
		for (int i = 0; i < b_s; i++){
			b[i] = rand() % 16 + 1;
		}
	}
	else if(answer == 2) {
		for (int i = 0; i < a_s; i++) {
			cout << "a[" << i + 1 << "]: ";
			cin >> a[i];
		}
		for (int i = 0; i < b_s; i++) {
			cout << "b[" << i + 1 << "]: ";
			cin >> b[i];
		}
	}

	bubble_sort(a, a_s);
	bubble_sort(b, b_s);

Тут самым коротким решением оказалось решение глубокоуважаемого @abyrkov
int	counter1 = 0,
		counter2 = 0,
		counter3 = 0;

	for (int counter = 0; counter < (a_s + b_s) / 2; counter++)
	{
		if (a[counter1] <= b[counter2]) {
			counter3 = a[counter1];
			counter1++;
		}
		else {
			counter3 = b[counter2];
			counter2++;
		}
	}
	cout << counter3;
	system("pause");
	return 0;
}
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
@res2001
Developer, ex-admin
В таком объеме данных наверняка очень большое количество повторяющихся значений.
Можно попробовать собрать некую статистику:
значение - количество
по каждому значению.
Отсортировать и искать медиану по статистическим значениям.
Объем, видимо, будет все равно большой, но уже не террабайты.
Или, не собирать статистику, а двигаясь одновременно по обоим массивам считать количество значений. На каком элементе достигнете медианного положения - это значение и будет медианой.
Если значения в массиве одной длины (например 32 битные целые), то исходя из общего объема массивов легко вычислить положение медианного элемента. Так же пользуясь тем, что массивы отсортированы можно довольно быстро находить количество каждого конкретного значения.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы