第3关：找出数组中第 k 个小的元素

这道题目需要我们在一个数组中找出第 k 个小的元素。具体的做法可以使用快速选择算法，也就是快速排序的变种。我们可以先选取一个枢轴元素，然后将数组中小于枢轴的元素放在左边，大于枢轴的元素放在右边，这样枢轴元素就排在了正确的位置上。然后我们可以比较枢轴元素的位置和 k 的大小关系，如果 k 小于枢轴元素的位置，那么我们就在左边的子数组中继续查找第 k 小的元素；如果 k 大于枢轴元素的位置，那么我们就在右边的子数组中继续查找第 k 小的元素。这样不断递归下去，直到找到第 k 小的元素为止。

相关问题

找出数组中第 k 个小的元素

可以使用快速选择算法来找出数组中第 k 个小的元素。

快速选择算法的基本思想是，选择一个基准元素，将数组中小于基准元素的元素放在基准元素的左边，将大于基准元素的元素放在基准元素的右边，然后比较基准元素的位置和 k 的大小关系，如果基准元素的位置等于 k，就找到了第 k 个小的元素，如果基准元素的位置大于 k，就在基准元素的左边继续查找，如果基准元素的位置小于 k，就在基准元素的右边继续查找。

以下是使用快速选择算法找出数组中第 k 个小的元素的 Python 代码：

def quick_select(nums, k):
    pivot = nums[0]
    left = [x for x in nums if x < pivot]
    right = [x for x in nums if x > pivot]
    mid = [x for x in nums if x == pivot]
    if k <= len(left):
        return quick_select(left, k)
    elif k <= len(left) + len(mid):
        return pivot
    else:
        return quick_select(right, k - len(left) - len(mid))

在这个函数中，我们首先选择数组中的第一个元素作为基准元素 pivot。然后，我们将数组分成三个部分：小于 pivot 的元素放在 left 数组中，大于 pivot 的元素放在 right 数组中，等于 pivot 的元素放在 mid 数组中。接下来，我们比较基准元素的位置和 k 的大小关系，如果基准元素的位置等于 k，就返回基准元素的值，如果基准元素的位置大于 k，就在 left 数组中继续查找第 k 个小的元素，如果基准元素的位置小于 k，就在 right 数组中继续查找第 k - len(left) - len(mid) 个小的元素。

这个函数的时间复杂度为 O(n)，其中 n 是数组的长度。

找出数组中第 k 个小的元素C语言

可以使用快速选择算法来找出数组中第 k 小的元素。

以下是示例代码：

#include <stdio.h>

int partition(int* arr, int left, int right) {
    int pivot = arr[right];
    int i = left - 1;

    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    int temp = arr[i + 1];
    arr[i + 1] = arr[right];
    arr[right] = temp;

    return i + 1;
}

int quickSelect(int* arr, int left, int right, int k) {
    if (left == right) {
        return arr[left];
    }

    int pivotIdx = partition(arr, left, right);
    int numSmaller = pivotIdx - left + 1;

    if (numSmaller == k) {
        return arr[pivotIdx];
    } else if (numSmaller > k) {
        return quickSelect(arr, left, pivotIdx - 1, k);
    } else {
        return quickSelect(arr, pivotIdx + 1, right, k - numSmaller);
    }
}

int main() {
    int arr[] = {5, 7, 2, 8, 4, 6, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;

    int kthSmallest = quickSelect(arr, 0, n - 1, k);

    printf("The %dth smallest element is %d\n", k, kthSmallest);

    return 0;
}

在上面的代码中，`partition()` 函数实现了快速排序中的分区操作，将数组分成两部分，左边的元素都小于等于枢轴元素，右边的元素都大于枢轴元素。

`quickSelect()` 函数则使用快速选择算法来找出数组中第 k 小的元素。它首先通过调用 `partition()` 函数将数组分成两部分，然后计算出左半部分的元素个数 `numSmaller`。如果 `numSmaller` 等于 k，那么枢轴元素就是第 k 小的元素。如果 `numSmaller` 大于 k，那么第 k 小的元素一定在左半部分，递归调用 `quickSelect()` 函数来处理左半部分。如果 `numSmaller` 小于 k，那么第 k 小的元素一定在右半部分，递归调用 `quickSelect()` 函数来处理右半部分，同时需要将 k 减去左半部分的元素个数。

在上面的示例中，数组 `{5, 7, 2, 8, 4, 6, 3}` 中第 3 小的元素是 4。