随机选择

习题预习

1. 在一个包含n个元素的未排序数组中找到第k个最小元素。
2. 给定一个含有n个元素的未排序数组，找到其中第k个最大元素。
3. 在一个包含n个元素的未排序数组中找到中位数。
4. 找到一个数组中的第i个元素，使得它左边的元素都比它小，右边的元素都比它大。
5. 找到一个数组中最接近中位数的元素。

说明知识

Randomized Selection是一种选择性能比QuickSort还要优异的算法，可以在O(n)的时间复杂度内选择一个阵列中第k小（大）的元素。

该算法的基本思想是选择一个随机数作为pivot（基准点），将阵列分为两个部分，一部分比pivot小，一部分比pivot大。然后判断第k小（大）的元素在哪个部分中，进行分治递归操作，直到找到第k小（大）的元素为止。

以下是一个说明Randomized Selection的Python代码范例：

import random

def randomized_selection(arr, k):
    if len(arr) == 1:
        return arr[0]
    pivot = random.choice(arr)
    left = [x for x in arr if x < pivot]
    right = [x for x in arr if x > pivot]
    mid = [x for x in arr if x == pivot]
    if k <= len(left):
        return randomized_selection(left, k)
    elif k > len(left) + len(mid):
        return randomized_selection(right, k-len(left)-len(mid))
    else:
        return mid[0]

在这个例子中，我们首先选择随机pivot，然后将阵列分成三部分：比pivot小的元素、比pivot大的元素、和等于pivot的元素。接着，我们判断第k小（大）的元素在哪个部分中，进行分治递归操作。如果k小于等于左边部分的元素个数，那么第k小的元素必然在左边，我们就递归对左边的阵列进行操作。如果k大于左边部分的元素个数加上等于pivot的元素个数，那么第k小的元素必然在右边，我们递归对右边的阵列进行操作。如果k介于左边部分的元素和等于pivot的元素的个数之间，那么第k小的元素就是pivot本身。

以上就是Randomized Selection的基本概念和使用范例。该算法通常比其他排序算法效率更高，因为它采用随机pivot，可以避免最坏情况下的时间复杂度。

条列重点

1. Randomized Selection是一种利用随机化算法来找到数组中第k小元素的算法。

2. 该算法的关键是在每一次遍历数组时随机选择一个pivot元素，把小于pivot的元素放到pivot左边，大于pivot的元素放到pivot右边，然后根据pivot的位置决定接下来的操作。

3. 如果pivot的位置恰好是k-1，那么第k小元素就是pivot；如果pivot的位置小于k-1，则在右侧子数组中递归查找第k-pivot位置的元素；如果pivot的位置大于k-1，则在左侧子数组中递归查找第k个元素。

4. 该算法的时间复杂度为平均情况下O(n)，最坏情况下O(n^2)。

5. 为了避免最坏情况的发生，可以在每次递归时随机选择pivot，而不是固定选择数组的第一个元素或最后一个元素。

6. Randomized Selection常用于解决第k小元素或第k大元素的问题，例如找到中位数或top k问题。

7. 总之，Randomized Selection是一种简单、高效的算法，适用于快速查找数组中第k小元素。

知识测验

1. 给定一个整数数组和一个整数k，找出数组中第k小的元素。

答案：使用Randomized Selection算法，平均时间复杂度为O(n)。

2. 在给定的整数数组中找到第二大的数。

答案：实现Randomized Selection，将每个元素与第一个标兵进行比较，然后将数组切分到第二大的数为止。

3. 给定一个未排序的数列，找出其中的中位数。

答案：使用Randomized Selection算法，从中选择一个标兵元素，然后比较将数组切分为左右两个子数组。

4. 给定一个数列，找到其中第k个重复出现的元素。

答案：使用Randomized Selection算法找到第k小元素，然后在剩余的数组中进行线性查找。

5. 给定一个整数数组，找到最大的k个元素。

答案：使用Randomized Selection算法，将数组切分为左右两部分，递归查找前k大的元素，然后归并两个子数组。