Самый быстрый способ найти медиану в динамически растущем диапазоне
Может кто-нибудь предложить какие-либо методы или ссылку на реализации быстрого медианного поиска для динамических диапазонов в C ++? Например, предположим, что для итераций в моей программе диапазон увеличивается, и я хочу найти медиану при каждом запуске.
Range
4
3,4
8,3,4
2,8,3,4
7,2,8,3,4
Таким образом, приведенный выше код в конечном итоге даст 5 средних значений для каждой строки.
Решение
Лучшее, что вы можете получить, не отслеживая отсортированную копию массива, — это повторно использовать старую медиану и обновлять ее с помощью поиска в линейном времени следующего по величине значения. Это может показаться простым, но есть проблема, которую мы должны решить.
Рассмотрим следующий список (отсортированный для облегчения понимания, но вы держите их в произвольном порядке):
1, 2, 3, 3, 3, 4, 5
// *
Итак, медиана 3 (средний элемент, поскольку список отсортирован). Теперь, если вы добавите число, которое больше медианы, это потенциально «сдвигает» медиану вправо на половину индекса. Я вижу две проблемы: Как мы можем продвинуться на половину индекса? (По определению медиана — это среднее значение следующих двух значений.) И как мы узнаем, при каком 3 медиана была, когда мы знаем только медиана 3?
Эту проблему можно решить, сохранив не только текущую медиану, но и позиция медианы в числах того же значения, здесь он имеет «смещение индекса» из 1, так как это второй 3, Добавление числа больше или равно 3 в списке изменяется смещение индекса на 1.5, Добавление числа меньше 3 меняет его на 0.5,
Когда это число становится меньше нуля, медиана изменяется. Это также должно измениться, если оно выходит за пределы числа равных чисел (минус 1), в этом случае 2Это означает, что новая медиана больше, чем последнее равное число. В обоих случаях вам нужно искать следующее меньшее / следующее большее число и обновлять медианное значение. Чтобы всегда знать, каков верхний предел для смещения индекса (в этом случае 2), вы также должны отслеживать количество равных чисел.
Это должно дать вам приблизительное представление о том, как реализовать медианное обновление за линейное время.
Другие решения
Плавники какой-то код ниже, я переделал это стек дать ваш необходимый вывод
private void button1_Click(object sender, EventArgs e)
{
string range = "7,2,8,3,4";
decimal median = FindMedian(range);
MessageBox.Show(median.ToString());
}
public decimal FindMedian(string source)
{
// Create a copy of the input, and sort the copy
int[] temp = source.Split(',').Select(m=> Convert.ToInt32(m)).ToArray();
Array.Sort(temp);
int count = temp.Length;
if (count == 0) {
throw new InvalidOperationException("Empty collection");
}
else if (count % 2 == 0) {
// count is even, average two middle elements
int a = temp[count / 2 - 1];
int b = temp[count / 2];
return (a + b) / 2m;
}
else {
// count is odd, return the middle element
return temp[count / 2];
}
}