长数组所有旋转的内存和省时排序

Question

我正在寻找以下问题的内存和省时的解决方案。很容易想到使用O（n ²）内存和O（n ² log n）时间（？）的基本算法，我想知道是否有一种算法可以（对于某些输入结构而言）显着提高了内存和时间效率。

Input：长度为n的数组a填充有非负整数。数组中的每个整数的大小均小于或等于b。我对n很大（几千万）而b相对很小的设置感兴趣。我们可以假设a中任何特定整数的出现次数都受m限制，其中m约为n / b。

考虑数组a的所有旋转的集合，即，如果a =（a ₁，a ₂，...，a _n），则其旋转为（ a ₁，a ₂，...，a _n），（a ₂，a ₃，...，a _{n] >，a 1），（a 3，a 4，...，a n，a 1，a 2） ，...，（a n，a 1，a 2，...，a n-1）。令r 1，r 2，...，r n表示数组a的旋转按字典顺序排序（递增）的顺序（使用0 <1 <2 <...>}

输出

：两个数组first和last，它们存储r ₁，r ₂，...，r _n根据排序顺序。

基本算法

（不是存储器，也不是省时的）：构造a的所有旋转并将其存储在矩阵A（使用O（n 2）存储器）中。定义排序例程（使用标准排序技术）以对A进行排序。提取排序后的矩阵的第一列和最后一列。估计排序步骤的最佳时间复杂度是O（n ^{2] log n），即，对于排序算法，将O（n log n）乘以每个成对比较的O（n）。}

第二算法

：我们可以遍历数组，并在数组中存储以小于或等于b的任何整数i开头的位置（这是O（n）时间和O（nm）内存操作） 。然后，我们可以生成以特定整数i开头的所有旋转，并根据基本算法对旋转矩阵进行排序（存储此矩阵使用O（nm）内存，排序可能需要O（mn log m）时间）。通过对每个从0到b的整数i重复该过程，很容易构造输出。

是否有使用定制排序策略的内存效率更高的方法？我满怀希望，因为存储输出只需要O（n）内存。

我正在寻找以下问题的内存和省时的解决方案。容易想到使用O（n2）内存和O（n2 log n）时间（？）的基本算法，我想知道是否存在...

Answer 1

为O（nlogn）中的给定数组计算suffix array。请注意，链接的实现对循环移位进行排序（在后缀中使用特殊字符-您不需要它）-正是您所需要的（但无需物理排序即可“排序”）

然后从后缀数组中提取由索引处理的初始数组元素-这是开始元素的列表（结束元素在先前的索引处。）>]

[P[0]包含最小循环移位的位置，因此A[P[0]]和A[P[0]-1]是第一对，P[1]-下一个最小移位的位置，依此类推

Answer 2

让我们构建一个更好的算法来查找第一个旋转。按字典顺序构造最后一个是相同的问题，但排序相反。我们需要跟踪的是最小旋转量，以及当前可能处于的位置。这是该想法的Python。

def min_rotation (elements):
    rotation = []
    positions = [i for i in range(len(elements))]
    while len(rotation) < len(elements):
        min_element = elements[positions[0]]
        new_positions = []
        for i in range(len(positions)):
            # Get the position and start rotating.
            position = positions[i]
            if elements[position] < min_element:
                min_element = elements[position]
            elif min_element <elements[position]:
                continue
            new_position = (position + 1) % len(elements)
            new_positions.append(new_position)
        positions = new_positions
        rotation.append(min_element)
    return rotation

Answer 3

构造包含R的辅助数组0..n-1，然后使用比较函数对R进行排序，该比较函数将每个参数作为相应旋转的起始索引。

运行：O

（n log n