如何设计一个算法，从n个数中找出第k个小的数，要求线性时间复杂度

要设计一个线性时间复杂度的算法找出第k个小的数，可以使用快速选择算法（QuickSelect）。快速选择算法是基于快速排序算法的变种，它通过每次选取一个基准元素，将数组划分为两个部分，其中一部分包含小于基准元素的数，另一部分包含大于基准元素的数。然后根据基准元素的位置来确定第k个小的数在哪个部分中，从而缩小搜索范围，重复这个过程直到找到第k个小的数。

以下是一个示例实现该算法的伪代码：

function quickSelect(arr, left, right, k)
    if left = right
        return arr[left]

    pivotIndex = partition(arr, left, right)  // 获取基准元素的位置

    if k = pivotIndex
        return arr[pivotIndex]
    else if k < pivotIndex
        return quickSelect(arr, left, pivotIndex - 1, k)  // 在左侧部分继续搜索第k个小的数
    else
        return quickSelect(arr, pivotIndex + 1, right, k)  // 在右侧部分继续搜索第k个小的数

function partition(arr, left, right)
    pivot = arr[right]  // 取最右边的元素作为基准元素
    i = left - 1
    
    for j = left to right - 1
        if arr[j] < pivot
            i = i + 1
            swap arr[i] and arr[j]
    
    swap arr[i + 1] and arr[right]  // 将基准元素放入正确的位置
    
    return i + 1

然后，你可以调用 `quickSelect` 函数来找到第k个小的数。假设数组为 `nums`，则调用 `quickSelect(nums, 0, n-1, k-1)` 即可，其中 `n` 是数组的长度。注意，由于数组下标是从0开始的，所以在调用时需要将k减去1。

该算法的时间复杂度为O(n)，其中n是数组的长度。但是在最坏情况下，时间复杂度可能达到O(n^2)，因此可以通过随机选择基准元素来避免最坏情况的发生。