Эффективно найти ряды элементов в массиве?

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, как обычно).

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

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

Answer 2

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

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

Answer 3

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

Answer 4

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

Answer 5

Если у вас нет массива, я не думаю, что это возможно сделать в 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 6

Я использовал это для быстрого и грязного в 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]

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

Answer 7

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

Вот как это сделать в 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]

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