arrays - 找到一种算法，在排序后根据数组的状态对其进行排序

Question

Let A be an array with n elements. A is not sorted, nonetheless, after sorting the array, the difference between any two adjacent elements would be either k₁, k₂ or k₃.

It should be noted that k₁, k₂ and k₃ are not given, and all of them are natural!

For example, given the array:

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

After sorting the array, we would get -

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

The difference between the first pair (5, 7) is 2; so k₁=2, the difference between the third pair (9,14) is 5, so k₂=5, whereas the difference between the fourth pair (14, 21) is 7, so k₃=7. The difference between other adjacent pairs is also 2, 5 and 7.

The algorithm for sorting the array should be as best as possible (obviously below O(nlogn)).

我设法回答了一个类似的问题，其中任意两个相邻元素之间的差异是 k、2k 或 3k，其中 k 是实数。但是我无法通过类似的方法找到合适的算法，通过找到 k，除以它并进行桶排序。
通过找到最小值和第二个最小值，我们可以找到 k 之一。但是 k 可能是 n2 - 所以找到最大值也无济于事......我真的迷路了!
免责声明:这个问题之前也有人问过，但是问题没有给出答案，问题也不好理解。

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