0

假设您有一个按升序排列的值列表，除了在某些时候它们会环绕

2, 4, 6, 9, 12, 15, 34, -2, 1, 4, 5, 7, ...

知道周期是 2^n，对于 n 的某个值，是否有任何内置函数，或者重新排列上述值的快速方法，以便所有数字都按升序排列（假设这些数字是可能的)?

4

4 回答 4

5

list.sort()可能足够快。在 CPython 中，它是使用Timsort实现的，它应该以优于平均水平的方式处理像你这样的情况（第一阶段是寻找已经排序的数字运行，就像你的情况一样）。

于 2012-04-26T21:56:23.423 回答
2

预期的输出将有助于理解您的问题。我猜到了与其他人不同的理想解决方案。也许其他人可以为这种解释找到更简洁的解决方案。

输出将是 2, 4, 6, 9, 12, 15, 34, 62, 65, 68, 69, ... 即从 -2 开始的所有值都向上移动 64

首先，我猜测周期大小为 64。这可以通过例如查看相邻元素的最负差异并四舍五入到 2 的幂来完成。如果您在开始时没有所有可用的值，这可能是不可能的。

period = 64

def unwrap(seq):
    it = iter(seq)
    try:
        lastitem = next(it)
    except StopIteration:
        return
    yield lastitem
    shift = 0
    for item in it: 
        if item < lastitem:
            shift += period
        yield item + shift
        lastitem = item

如果您需要列表而不是生成器，则可以使用

result = list(unwrap(original_list))
于 2012-04-27T00:20:34.303 回答
0

如果您希望所有值都按升序排列，那么这是一种：

>>> sorted([2, 4, 6, 9, 12, 15, 34, -2, 1, 4, 5, 7])
[-2, 1, 2, 4, 5, 6, 7, 9, 12, 15, 34]

您是在尝试根据连续数字间隔包装的知识来优化排序，还是提出不同的问题？

于 2012-04-26T21:56:31.843 回答
0 
>>> sorted([5, 2, 3, 1, 4])
[1, 2, 3, 4, 5]

>>> a = [5, 2, 3, 1, 4]
>>> a.sort()
于 2012-04-26T21:57:21.730 回答