Эффективно находить ранги элементов в массиве?

Как эффективно найти ранг каждого элемента массива, усредняя его в случае связей? Например: 

float[] rank(T)(T[] input) {
    // Implementation
}

auto foo = rank([3,6,4,2,2]);  // foo == [3, 5, 4, 1.5, 1.5]

Единственный способ, который я могу придумать, требует выделения 3 массивов:

  1. дубликат входного массива, потому что он должен быть отсортирован, а мы им не владеем.
  2. массив для отслеживания порядка сортировки входного массива.
  3. массив возвращаемых рангов.

Знает ли кто-нибудь, как это сделать за O (N log N) время и O (1) вспомогательное пространство (имеется в виду, что единственный массив, который мы должны выделить, - это тот, который мы собираемся вернуть) или, по крайней мере, избавиться от одного из трех массивов выше?

7 3
performance sorting algorithm statistics space-efficiency

7 ответов:

Вы можете выделить массив, который собираетесь вернуть (назовем его R), инициализировать его до 0..n-1, а затем "сортирует" входящий массив (называемый I), но используя сравнение I[R[k]] против I[R[j]] вместо обычного R[k] против R[j], а затем меняет значения в массиве R по мере необходимости (вместо значений в массиве I, как обычно).

Вы можете реализовать эту косвенную сортировку, используя либо quicksort, либо heapsort (или bubblesort, но это испортит вашу сложность).

Вам нужно только выделить один массив-и некоторое пространство стека для индексов.

4

Итак, вы дублируете входной массив в foo. Сортировка foo на месте за O (N log n) время с помощьюheapsort . Теперь возьмите первый элемент вашего входного массива и найдите его ранг в foo за O(log n) время с помощью двоичного поиска , вставьте ранг в массив ranks и верните его.

Теперь вы используете 2 массива вместо 3.

2

Если вы не владеете массивом, я не думаю, что это возможно сделать в O(N log N) и в пространстве O(1).

Если диапазон элементов (насколько большим может быть элемент) мал, используйте подсчет. Подсчитайте, сколько существует каждого элемента, а затем вычислите результирующий массив на основе входного массива с помощью Счетного массива.

c - is counting result,
C - is cumulative counting
C[i] = c[i] + c[i-1] + c[i-2] + ... + c[0]
result[i] = 1 / c[in[i]] + C[in[i]-1]
0

Почему бы просто не скопировать и не отсортировать массив и не перейти оттуда? Существует множество алгоритмов сортировки на месте, таких как heapsort.

0

Возможно, было бы полезно обобщить ответ Флорина (и связанные с ним комментарии) с помощью некоторого простого кода.

Вот как это сделать в Ruby: 

arr = [5,1,0,3,2,4]
ranks = (0..arr.length-1).to_a.sort_by{ |x| arr[x] }
# ranks => [2, 1, 4, 3, 5, 0]

И в Python: 

arr = [5,1,0,3,2,4]
ranks = range(len(arr))
ranks.sort(key=lambda x:arr[x])
# ranks => [2, 1, 4, 3, 5, 0]

Массив рангов говорит вам, что 0 имеет ранг 2, 1 имеет ранг 1, 2 имеет ранг 4 и т. д. (Конечно, эти ранги начинаются с нуля, а не с единицы.)

0

Как насчет использования бинарного дерева поиска и вставки элементов один за другим в это BST. Затем ранг можно определить, сохраняя счетчик на всех элементах, появляющихся слева от узла элемента, который мы хотим найти, используя ранг для обхода BST.

0

Я использовал это для быстрого и грязного выполнения в python: 

def rank(X):
    B = X[:]
    B.sort()
    return [ float(B.index(x)+1) for x in X]

def rank(X):
    B = X[:]
    B = list(set(B))
    B.sort()
    return [ float(B.index(x)+1) for x in X]
Первый пример будет работать в том случае, если у вас нет дубликатов в исходном списке. Это можно сделать лучше, но я играл с некоторыми хаками и вышел с этим. Второй вариант будет работать, если у вас есть дубликаты.
0