Нашли разницу меньше среднего в несортированном массиве?

Мне нужно найти 2 элемента в несортированном массиве так, чтобы разница между ними была меньше или равна (Максимум - Минимум) / (количество элементов в массиве).

В O (n).

Я знаю максимальные и минимальные значения.

Кто-нибудь может что-то придумать?

Спасибо!

15.12.2008 12:12:43
@ Binary Worrier: какая разница? ;-)
splattne 15.12.2008 12:15:15
@ Splattne много, но это означает, по крайней мере, ретаг
Greg Dean 15.12.2008 12:16:14
@ Грег Дин: о, это РАЗНОЕ! ;-)
splattne 15.12.2008 12:17:15
@Splattne: Часть моей работы - наставлять начинающих программистов на разных уровнях. Предоставление полного ответа мало помогает ученику. Если это домашнее задание, я дам полезные советы о том, как решить проблему, не давая полного решения. Также +1 Грег Дин, его нужно пометить заново
Binary Worrier 15.12.2008 12:22:09
Таким образом, можно исправить название «diffrence» сам и другие орфографические ошибки. Тогда никто не поймет мой «забавный» комментарий. ;-)
splattne 15.12.2008 12:33:25
3 ОТВЕТА

Шаг 1: Используйте Bucket Sort . Не сортируйте отдельные ведра.

Должно быть довольно очевидно, что делать отсюда и как определять размеры ведер.

3
15.12.2008 16:31:33
Это правильное решение. Я не уверен насчет «довольно очевидного», единственное, о чем нужно беспокоиться, это две ситуации, которые нужно проверить: одна, где в одной дырке есть более одного пиджона, и одна, где во всех пиджон-дырах ровно 1 пиджон.
Jimmy 15.12.2008 16:50:50
Сид Датта вдавается в подробности.
Brian 15.12.2008 21:56:14
  1. Количество ведер = 2n.

    значения в каждом ведре = (min + k((max-min)/2n)) <= value < (min + (k+1)((max-min)/2n)).

    0 <= k <2n

    Диапазон каждого ведра = ((max-min)/2n)

  2. Назначьте каждый элемент в ведра. Не сортируйте внутри ведра.

  3. Если какое-либо ведро имеет более 1 элемента, максимально возможная разница между ними составляет ((max-min)/2n). Следовательно, у вас есть свой ответ.

  4. Если в любых двух последовательных сегментах содержится более нуля элементов, то максимальная разница между ними равна ((max-min)/2n)*2 = ((max-min)/n). Следовательно, у вас есть свой ответ.

1
15.12.2008 21:47:28
это работает, хотя вы можете обойтись с n сегментами, вам просто нужно сравнить последовательные значения.
Jimmy 15.12.2008 21:56:28
Я думаю, что это пропускает решение в некоторых случаях. Что делать, если n элементов появляются в альтернативных сегментах, поэтому в строке никогда не бывает двух непустых сегментов, но есть одно значение около «верха» сегмента j и другое значение около «низа» сегмента j + 2. Они меньше чем (max-min) / n друг от друга.
Steve Jessop 16.12.2008 19:34:42
Однако, как говорит Джимми, в этом случае сегменты полностью отсортировали массив, что означает, что вы можете закончить пропуском O (n), чтобы либо найти решение, либо доказать, что его нет.
Steve Jessop 16.12.2008 19:35:45

Правильный вопрос должен быть следующим: в массиве A = [a0, a2, .. an] найти два элемента a, b, таких, что разница между ними меньше или равна: (Mm) / 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 n + d) + 0,5 (c n + d) + 0,25 (c * n + d) +… + (1 / log_ {2} (n)) (c n + d) <=

<= (1 + 0,5 + 0,25 +….) D + (c * n + 0,5 * c n +….) = (1 + 0,5 + 0,25 +….) D + c n (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])
1
4.12.2018 15:00:12