Расположите список по порядку

Question

У меня есть список {10,5,3,9,12}. Мне нужно преобразовать его в подобное {3,1,0,2,4}. Я имею в виду присвоить 0 наименьшему значению, 1 - следующему наименьшему значению и т. Д.

мой код:

     list = {2,3,10,5,1};
     for (int i =list.Count-1; i >= 0 ; i--)
        {

            var maxNo = list.Max();
            var smallIndex = list.IndexOf(maxNo);
            list[smallIndex] = i * -1;

        }
        for (int i = 0; i < list.Count; i++)
        {
            list[i] = list[i] * -1;
        }
        // prints {1,2,4,3,0}

Примечание : список будет содержать только положительные числа.

Выше кода хорошо. Нужна помощь в этом.

Answer 1

По сути, вам просто нужно отсортировать список. Посмотрите на алгоритмы сортировки.

Вы можете создать другой список, содержащий ваши исходные числа в паре с целочисленными индексами от 0 до длины списка, например {{10,0}, {5，1}, {3,2}, {9,3}, {12,4}}, отсортировать этот список с помощью встроенной функции сортировки вашего языка программирования, а затем извлечь целочисленные индексы.

РЕДАКТИРОВАТЬ: Ваша программа будет работать, но она довольно хакерская (с использованием этих отрицательных чисел) и очень неэффективная. Он проходит список дважды для каждого элемента, чтобы найти максимум и найти индекс максимума. Я бы посоветовал вам немного прочитать об алгоритмах сортировки.

EDIT2: практическая реализация этого может означать использование другой функции сравнения для sort: предположим, что ваш исходный список называется array. Создайте другой массив idx = {0,1,2,3,4} и отсортируйте его не на основе функции сравнения x < y, а array[x] < array[y].

CORRECTION

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

Answer 2

это O(2 (n log n)), поскольку сортируется дважды.сначала он превращает список в список (index, value) сортировок по значению v и добавляет отсортированные позиции s и сортирует по индексу, а затем извлекает отсортированные позиции.

>>> list( s for s, i in sorted( ( (s,i) for s,(i,v) in enumerate(sorted( ( (i,v) for i,v in enumerate([10,5,3,9,12]) ), key=lambda t: t[1] )) ), key=lambda t: t[1] ) )
[3, 1, 0, 2, 4]

или в несколько строк (обратите внимание, что это может сохранить память дольше, чем требуется):

def arrange(l):
    a = sorted( ( (i,v) for i,v in enumerate(l) ), key=lambda t: t[1] )
    b = sorted( ( (s,i) for s,(i,v) in enumerate(a) ), key=lambda t: t[1] )
    return list( s for s, i in b )

print arrange([10,5,3,9,12])

Answer 3

Ваш алгоритм работает для списка неотрицательных целых чисел, но, как отмечали другие, он неэффективен из-за повторного вычисления максимального значения.

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

То, что вы ищете в своем примере {2,3,10,5,1} сопоставления с {1,2,4,3,0}, представляет собой список индексов, которые ваш исходный список будет занимать в отсортированном списке.

Наиболее естественный способ добиться этого - сортировка, индексация и «сортировка» следующим образом (и как это реализовано в более кратком решении Дана Д.):

Добавить индексный столбец к исходным данным:

{2,3,10,5,1} => {(2,0), (3,1), (10,2), (5,3), (1,4)}

Сортировать по оригинальному столбцу:

{(2,0), (3,1), (10,2), (5,3), (1,4)} => {(1,4), (2,0), (3,1), (5,3), (10,2)}

Добавить еще один индексный столбец:

{(1,4), (2,0), (3,1), (5,3), (10,2)} => {(1,4,0), (2,0,1), (3,1,2), (5,3,3), (10,2,4)}

Вернитесь к исходному порядку, отсортировав по первому столбцу индекса:

{(1,4,0), (2,0,1), (3,1,2), (5,3,3), (10,2,4)} => {(2,0,1), (3,1,2), (10,2,4), (5,3,3), (1,4,0)}

Удалите исходный столбец и первый столбец индекса, оставив только индекс, добавленный в середине, который теперь помещен в правильную позицию:

{(2,0,1), (3,1,2), (10,2,4), (5,3,3), (1,4,0)} => {1,2,4,3,0}

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

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

Answer 4

Это будет работать, но использование list.IndexOf(maxNo) один раз для каждого элемента приводит к времени O (n ^ 2). Было бы более эффективно отсортировать список, за исключением того, чтобы поддерживать индексный массив таким образом, чтобы ix [i] был i-м по величине элементом. Другими словами, сравните список [i], но назначьте ix [i] в ​​сортировке. Это также будет работать с отрицательными числами.

Answer 5

Сортируйте копию списка, поместите ее в структурированную структуру данных с элементами списка в качестве ключей и положением в отсортированном списке в качестве значения.Сопоставьте исходный список с использованием ключевой структуры данных.knlogn + 2n = O (nlogn) производительность.