Перестановка чисел в мин и макс форме

Question

С учетом следующего ввода

[1,2,3,4,5,6,7]

Предполагается, что числа отсортированы так, чтобы они сортировались следующим образом

[7,1,6,2,5,3,4]

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

def maxMin(lst):
    result = []
    left = 0
    right = len(lst) - 1
    while left < right:
        result.append(lst[right])
        result.append(lst[left])
        left += 1
        right -= 1
    if len(lst) % 2 != 0:
        result.append(lst[left])
    return result

Хотя это решение работает, очевидно, оно использует дополнительное пространство, и существует возможный способ найти решение, которое использует только постоянное пространство. Я наткнулся на это видео на YouTube, но я понятия не имел, как автор придумал решение. Для меня понимание достижения решения более важно, чем фактическое решение. Я был бы рад, если бы кто-то смог пролить свет.

Answer 1

Жалуется на дополнительное место, потому что вы создаете второй список для хранения результата. С небольшим количеством данных это вполне разумный способ go об этом. Но если в вашем списке тысячи записей вместо нескольких, создание копии может оказаться невозможным. В этом случае вам может понадобиться переместить элементы списка на место .

Мы начнем с наблюдения, что список отсортирован и элементы в последней половине списка перемещены в ранее в списке, в четных позициях (0, 2, 4). Итак, сначала посчитайте, сколько элементов должно быть смещено на ранее в списке. Затем для каждого из элементов, подлежащих смещению, вычислите его новую позицию (0, 2, 4) и переместите его туда.

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

Примерно так:

a = [1,2,3,4,5,6,7]
shifts = len(a)//2
for i in range(shifts):
    print(f"shifting {a[-1]} to position {i*2}")
    a.insert(i*2,a.pop())
print (a)

Вывод из последнего вызова print() это [7, 1, 6, 2, 5, 3, 4]. print() вызов внутри l oop просто для того, чтобы показать вам, что происходит.

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

Answer 2

Существует стратегия сортировки на месте, которая минимизирует перемещения памяти (я полагаю, что вставка в список перераспределяет его внутри). Он основан на простом алгоритме сортировки, который меняет значение в каждой позиции, а последующая позиция имеет наименьшее значение. С небольшой поправкой к логике c мы можем сделать так, чтобы сортировка решила, что каждая позиция поочередно меняет самое низкое и самое высокое значение в зависимости от того, является ли позиция нечетной или четной.

Это место сортировки будет выполнить N перестановок и N * (N-1) / 2 сравнений, чтобы затраты памяти были минимальными и перераспределения не было.

def updownSort(a):
    for i in range(len(a)-1):         # for each position except the last one
        p=i                           # identify the swapping position (p)
        for j in range(i+1,len(a)):        # only look in remaining positions
            if bool(i&1) == (a[p]>a[j]):   # alternate seeking the largest and smallest value
                p = j
        a[p],a[i] = a[i],a[p]              # make the swap with the index that was found

a =  [1,2,3,4,5,6,7]

updownSort(a)
print(a)
# [7, 1, 6, 2, 5, 3, 4]

Обратите внимание, что любой другой алгоритм "сортировка на месте" (например, пузырьковый) sort) может быть адаптирован таким же образом, при условии, что сравнения могут учитывать сравниваемые позиции в дополнение к значениям.