Эффективное обнаружение рангов элементов в массиве?

Question

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

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) вспомогательном пространстве (что означает, что мы должны выделить только один массив, который мы собираемся вернуть) или по крайней мере, избавиться от одного из трех массивов выше?

Answer 1

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

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

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

Answer 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] 

Answer 3

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

Answer 4

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

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

Answer 5

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

Вот как сделать это в 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 и т. д. (Конечно, эти ранги начинаются с нуля, а не с одного.)

Answer 6

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

Answer 7

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

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] 

Первый пример будет работать в случае, если вы не имеете дубликаты в исходном списке. Это можно сделать лучше, но я играл с некоторыми хаками и выходил с этим. Второй будет работать, если у вас есть дубликаты.