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

Question

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

In O (n).

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

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

Спасибо!

Answer 1

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

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

Answer 2

Правильный вопрос должен быть: в массиве 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 n + d) + 0,5 (c n + d) + 0,25 (c * n + d) +… + (1 / log_ {2} (n )) (с n + d) <= </p>

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

Answer 3

1. Количество ведер = 2n.

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

   0 <= k <2n </p>

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

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

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

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