Обнаружили разницу меньше среднего в несортированном массиве?
Мне нужно найти 2 элемента в несортированном массиве, чтобы разница между ними была меньше или равна (Максимум - Минимум) / (количество элементов в массиве).
В O (n).
Я знаю максимальное и минимальное значения.
Кто-нибудь может что-нибудь придумать?
Спасибо!
@splattne много, но значит как минимум ретэг
@ Грег Дин: о, в этом РАЗНИЦА! ;-)
@Splattne: Часть моей работы - наставлять молодых программистов на разных уровнях. От простого предоставления полного ответа ученику мало пользы. Если это домашнее задание, я дам полезные советы, как решить проблему, не давая полного решения. Также +1 Грег Дин, его нужно пометить заново.
Так что это нормально, если я исправлю заголовок «различие» и другие орфографические ошибки. Тогда никто не поймет моего "смешного" комментария. ;-)
Упс, совсем пропустил, очень устал сегодня, прости, Сплаттне :)
Что делать, если решения не существует? Например, массив {3, 4} имеет max = 4, min = 3, n = 2, и ни одна пара элементов не имеет разницы, меньшей или равной (4-3) / 2 = 0,5.
@onebyone: по определению всегда есть одна пара чисел, которая решает проблему
Итак, каково решение в случае, который я даю, где массив равен {3,4}? Это, конечно, не «3 и 4», поскольку их разница равна 1, что больше заявленной границы. Я считаю, что проблема сформулирована неправильно. Если вы не имеете в виду «они не дали бы вам входной массив без решения».
Есть совсем другая проблема, которая, я думаю, может быть предполагаемой, где решение гарантировано, и способ доказательства наличия решения также предусматривает алгоритм O (n) для его поиска. В нем участвуют голуби.
@onebyone: черт, ты прав. Как говорилось ранее, я очень устал сегодня и, не думая ясно, я действительно думал о 3 и 4 (позор). Честный вопрос. Есть ли смысл в моей подсказке ниже? Я уже не могу сказать, если это не так, я удалю его. Спасибо.
@ Джек: Возможно, я ошибся, приятель, тысячу извинений, если у меня есть. Я подумаю над этим еще немного, это интересная проблема. Я удалил свой ответ. Спасибо также onebyone
Зависит от того, в чем должен быть вопрос, но я подозреваю, что то, что вы сказали, не приводит к решению. Конечно, это не приводит к решению, которое я имею в виду для вопроса, который я имею в виду, но я легко могу ошибиться.
@jack, не могли бы вы предоставить несколько примеров входных данных и ожидаемого решения? Я согласен с @onebyone, решение не представляется возможным.
Ответы 3
Шаг 1: Используйте Сортировка по ведру. Не сортируйте отдельные ведра.
Должно быть довольно очевидно, что делать дальше и как определять размеры ведер.
Это правильное решение. Я не уверен насчет «довольно очевидного». Единственное, о чем следует беспокоиться, - это две ситуации, которые нужно проверить: одна, когда в одной лунке есть более одного голубя, и другая, когда все петлицы имеют ровно 1 петуха.
Сид Датта говорит более подробно.
Количество ковшей =
2n.значения в каждом сегменте =
(min + k((max-min)/2n)) <= value < (min + (k+1)((max-min)/2n)).0 <= k <2n
Диапазон каждого ковша =
((max-min)/2n)Распределите каждый элемент по сегментам. Не сортируйте по ведрам.
Если в какой-либо корзине более 1 элемента, максимально возможная разница между ними составляет
((max-min)/2n). Значит, у вас есть ответ.Если в каждом из двух последовательных сегментов больше нуля элементов, максимальная разница между ними составляет
((max-min)/2n)*2 = ((max-min)/n). Значит, у вас есть ответ.
это работает, хотя вы можете обойтись n ведрами, вам просто нужно сравнить последовательные значения.
Я думаю, что в некоторых случаях это упускает из виду. Что, если n элементов появятся в альтернативных сегментах, поэтому в строке никогда не будет двух непустых сегментов, но есть одно значение рядом с «верхом» сегмента j, а другое значение - рядом с «низом» сегмента j + 2. Между ними меньше (макс-мин) / n.
Однако, как говорит Джимми, в этом случае сегменты полностью отсортировали массив, а это означает, что вы можете закончить проходом O (n), чтобы либо найти решение, либо доказать, что его нет.
Правильный вопрос должен быть таким: в массиве A = [a0, a2, .. an] найдите два элемента a, b, разность между которыми меньше или равна: (M-m) / n> | а - б | где M = max (A) и m = min (A).
Решение, которое я предлагаю, - использовать quickSelect, временная сложность O (n) в ожидании. наихудший случай - O (n ^ 2). Это компромисс, потому что в большинстве случаев это O (n), но для этого требуется сложность пространства O (1) (если quickSelect реализован итеративно, а мой псевдокод реализован с циклом while вместо рекурсии).
суть:
На каждой итерации мы находим медиану с помощью quickSelect, если |max - medianValue | > |min - medianValue | знаем, что мы должны искать в левой части массива. Это потому, что у нас одинаковое количество элементов с обеих сторон, но среднее значение ближе к минимуму, поэтому должны быть элементы с меньшей разницей между ними. В противном случае мы должны искать с правой стороны.
каждый раз, когда мы это делаем, мы знаем, что новый максимум или минимум subArray должен быть медианой. продолжаем поиск, каждый раз деля размер массива на 2.
доказательство времени выполнения в ожидании: Предположим, что каждая итерация по n элементам принимает c * n + d в ожидании. таким образом, мы имеем:
(cп + г) + 0,5 (cп + г) + 0,25 (c * n + d) +… + (1 / log_ {2} (n)) (cn + d) <=
<= (1 + 0,5 + 0,25 +….) D + (c * n + 0,5 * cn +….) = (1 + 0,5 + 0,25 +….) d + cn (1 + 0,5 + 0,25 +….) =
= 2 * d + 2 * c * n
это означает, что у нас есть O (n) в ожидании.
псевдокод с использованием рекурсии:
run(arr):
M = max(arr)
m = min(arr)
return findPairBelowAverageDiff(arr,0,arr.length,m,M)
findPairBelowAverageDiff(arr, start, end, min, max) :
if start + 1 < end:
medianPos = start + (end - start) / 2
// median that is between start and end in the arr.
quickSelect(arr, start, medianPos, end)
if max - arr[medianPos] > arr[medianPos] - min:
return findPairBelowAverageDiff(arr, start, medianPos,
min, arr[medianPos])
else :
return findPairBelowAverageDiff(arr, medianPos,
end, arr[medianPos], max);
else :
return (arr[start], arr[start + 1])
@Binary Worrier: какая разница? ;-)