5

我必须将数组的元素分成 3 组。这需要在不对数组进行排序的情况下完成。考虑这个例子

我们有 120 个未排序的值，因此最小的 40 个值需要在第一组中，接下来的 40 个在第二组中，最大的 40 个在第三组中

我正在考虑中位数方法的中位数，但无法将其应用于我的问题，请建议一种算法。

4

3 回答 3

6

您可以在阵列上调用quickselect两次来就地执行此操作，平均情况下是线性时间。最坏情况的运行时间也可以通过使用中值的线性时间中值算法来选择快速选择的最佳枢轴来改进到 O(n)。

对于对 quickselect 的两次调用，使用 k = n / 3。在第一次调用时，对整个数组使用 quickselect，在第二次调用时，从 arr[k..n-1] 使用它（对于 0 索引数组）。

维基百科对快速选择的解释：

快速选择使用与快速排序相同的整体方法，选择一个元素作为枢轴，并根据枢轴将数据分成两部分，相应地小于或大于枢轴。然而，不像在快速排序中那样递归到两侧，快速选择只递归到一侧——它正在搜索的元素所在的一侧。这将平均复杂度从 O(n log n)（快速排序）降低到 O(n)（快速选择）。

与快速排序一样，快速选择通常作为就地算法实现，除了选择第 k 个元素之外，它还对数据进行部分排序。有关与排序的联系的进一步讨论，请参见选择算法。

要将数组的元素分成 3 组，请结合使用以下用 Python 编写的算法和快速选择：

k = n / 3

# First group smallest elements in array
quickselect(L, 0, n - 1, k) # Call quickselect on your entire array

# Then group middle elements in array
quickselect(L, k, n - 1, k) # Call quickselect on subarray

# Largest elements in array are already grouped so
# there is no need to call quickselect again

这一切的关键在于快速选择使用了一个称为分区的子例程。分区将数组分成两部分，大于给定元素的部分和小于给定元素的部分。因此，它围绕该元素对数组进行部分排序并返回其新的排序位置。因此，通过使用快速选择，您实际上对第 k 个元素周围的数组进行了部分排序（请注意，这与实际对整个数组进行排序不同）就地和平均情况下的线性时间。

快速选择的时间复杂度：

  1. 最坏情况性能 O(n 2 )
  2. 最佳案例性能 O(n)
  3. 平均案例性能 O(n)

quickselect 的运行时间几乎总是线性的而不是二次的，但这取决于这样一个事实，即对于大多数数组，简单地选择一个随机枢轴点几乎总是会产生线性运行时间。但是，如果您想提高快速选择的最坏情况性能，您可以选择在每次调用之前使用中位数算法来逼近用于快速选择的最佳枢轴。这样做，您会将快速选择算法的最坏情况性能提高到 O(n)。这种开销可能不是必需的，但是如果您正在处理大量随机整数列表，它可以防止您的算法出现一些异常的二次运行时。

这是 Python 中的一个完整示例，它实现了快速选择并将其应用于 120 个整数的反向排序列表并打印出三个结果子列表。

from random import randint


def partition(L, left, right, pivotIndex):
    '''partition L so it's ordered around L[pivotIndex]
       also return its new sorted position in array'''
    pivotValue = L[pivotIndex]
    L[pivotIndex], L[right] = L[right], L[pivotIndex]
    storeIndex = left
    for i in xrange(left, right):
        if L[i] < pivotValue:
            L[storeIndex], L[i] = L[i], L[storeIndex]
            storeIndex = storeIndex + 1
    L[right], L[storeIndex] = L[storeIndex], L[right]
    return storeIndex


def quickselect(L, left, right, k):
    '''retrieve kth smallest element of L[left..right] inclusive
       additionally partition L so that it's ordered around kth 
       smallest element'''
    if left == right:
        return L[left]
    # Randomly choose pivot and partition around it
    pivotIndex = randint(left, right)
    pivotNewIndex = partition(L, left, right, pivotIndex)
    pivotDist = pivotNewIndex - left + 1
    if pivotDist == k:
        return L[pivotNewIndex]
    elif k < pivotDist:
        return quickselect(L, left, pivotNewIndex - 1, k)
    else:
        return quickselect(L, pivotNewIndex + 1, right, k - pivotDist)


def main():
    # Setup array of 120 elements [120..1]
    n = 120
    L = range(n, 0, -1)

    k = n / 3

    # First group smallest elements in array
    quickselect(L, 0, n - 1, k) # Call quickselect on your entire array

    # Then group middle elements in array
    quickselect(L, k, n - 1, k) # Call quickselect on subarray

    # Largest elements in array are already grouped so 
    # there is no need to call quickselect again

    print L[:k], '\n'
    print L[k:k*2], '\n'
    print L[k*2:]


if __name__ == '__main__':
    main()
于 2013-10-11T21:30:22.120 回答
1

我会看看订单统计。统计样本的第 k 阶统计量等于其第 k 个最小值。计算列表中第 k 个最小（或最大）元素的问题称为选择问题，由选择算法解决。

以中位数的方式思考中位数是正确的。但是，您可能希望从数组中找到第 20 个和第 40 个最小的元素，而不是找到中位数。就像找到中位数一样，使用选择算法只需线性时间即可找到它们。最后你遍历数组并根据这两个元素划分元素，这也是线性时间。

PS。如果这是您在算法课上的练习，这可能会对您有所帮助:)

于 2013-10-11T23:03:51.300 回答
0

分配一个与输入数组大小相同的数组，扫描输入数组一次，并跟踪数组的最小值和最大值。同时将第二个数组的所有值设置为 1。计算delta = (max - min) / 3。再次扫描数组并将第二个数组设置为两个，如果数字是 > min+delta and < max-delta; 否则if >= max-delta，将其设置为 3；结果，您将拥有一个数组，该数组告诉您该数字在哪个组中。我假设所有数字都彼此不同。复杂：O(2n)

于 2013-10-11T23:17:23.347 回答