Найти алгоритм сортировки массива по его статусу после сортировки

Question

Пусть A будет массивом с n элементами. A не сортируется, тем не менее после сортировки массива разница между любыми двумя соседними элементами будет либо k ₁ , k ₂ , либо k ₃ .

Следует отметить, что k ₁ , k ₂ и k ₃ не указаны, и все они натуральные!

Например, с учетом массива:

A = { 25, 7, 5, 9, 32, 23, 14, 21}

После сортировки массива мы получим -

A = { 5, 7, 9, 14, 21, 23, 25, 32}

Разница между первой парой (5, 7) составляет 2; поэтому k ₁ = 2, разница между третьей парой (9,14) составляет 5, поэтому k ₂ = 5, тогда как разница между четвертой парой (14, 21) равна 7, поэтому k ₃ = 7. Разница между соседними парами также составляет 2, 5 и 7.

Алгоритм сортировки массива должен быть как можно лучше (очевидно, ниже O (nlogn) ).

Мне удалось ответить на аналогичный вопрос, где разница между любыми двумя соседними элементами составляла k, 2k или 3k , где k - реальное. Но я не смог найти подходящий алгоритм, следуя аналогичному методу, найдя k , разделив его и выполнив сортировку сегментов.

Найдя минимум и второй минимум, мы можем найти один из k . Но k может быть n ² - поэтому поиск максимума тоже не поможет ... Я действительно потерян!

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

Answer 1

Вот O(n), который только не выглядит эффективным.

Идея проста. Учитывая минимальный элемент и список значений для k, вы создаете самый большой отсортированный набор со значениями k, которые вы уже нашли, находите наименьшую недостающую вещь, отсутствующую в наборе, и находите новое значение k. Если есть K значений k, эта операция будет O((1+K) * n).

Повторение этого K раз, следовательно, O((1+K)^2 * n).

В нашем случае K постоянная, поэтому мы получаем O(n).

Вот оно в Python.

def special_sort (array):
    # special cases first.
    if 0 == len(array):
        return array
    elif 1 == len(array):
        return array
    elif 2 == len(array):
        return [min(array), max(array)]

    min_value = min(array)
    values_of_k = []
    leftovers = array

    while len(leftovers):
        values_of_k = sorted(values_of_k)
        values = set(array)
        sorted_array = [min_value]
        values.remove(min_value)
        found = True
        while found:
            found = False
            for k in values_of_k:
                if sorted_array[-1] + k in values:
                    found = True
                    sorted_array.append(sorted_array[-1] + k)
                    values.remove(sorted_array[-1])
                    break

        leftovers = list(values)
        if 0 == len(leftovers):
            return sorted_array
        else:
            first_missing = min(leftovers)
            # Find the first element of the array less than that.
            i = -1
            while i+1 < len(sorted_array) and sorted_array[i+1] < first_missing:
                i = i+1
            values_of_k.append(first_missing - sorted_array[i])

print(special_sort([25, 7, 5, 9, 32, 23, 14, 21]))