在几个数中查找第k大的数 完整代码

好的，以下是一个简单的 Python 代码，可以在给定的一组数中查找第k大的数：

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

# 测试
nums = [3, 6, 9, 2, 8, 5]
k = 2
print(quick_select(nums, k)) # 输出第k大的数

这个算法的时间复杂度为O(n)，其中n是给定数列的长度。

相关问题

在几个数中查找第k大的数 完整代码 c++

好的，以下是一个完整的 C++ 代码，可以在给定的一组数中查找第k大的数：

#include <iostream>
#include <vector>
using namespace std;

int quick_select(vector<int>& nums, int k) {
    if (k < 1 || k > nums.size()) {
        return -1; // 输入的 k 不合法，返回 -1 表示查找失败
    }
    int pivot = nums[0];
    vector<int> left, mid, right;
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] < pivot) {
            left.push_back(nums[i]);
        } else if (nums[i] == pivot) {
            mid.push_back(nums[i]);
        } else {
            right.push_back(nums[i]);
        }
    }
    if (k <= right.size()) {
        return quick_select(right, k);
    } else if (k - right.size() <= mid.size()) {
        return mid[0];
    } else {
        return quick_select(left, k - right.size() - mid.size());
    }
}

int main() {
    vector<int> nums = {3, 6, 9, 2, 8, 5};
    int k = 2;
    int res = quick_select(nums, k);
    if (res == -1) {
        cout << "输入的 k 不合法！" << endl;
    } else {
        cout << "第 " << k << " 大的数是：" << res << endl;
    }
    return 0;
}

需要注意的是，如果输入的 k 不合法（即小于1或大于给定的数列长度），则返回 -1 表示查找失败，程序中也考虑了这种情况。

在几个数中查找第k大的数 完整代码 c++ 点击复制后，时间复杂度在O（n）

抱歉，可能我之前的回答有误。快速选择算法的时间复杂度平均情况下是O(n)，最坏情况下是O(n^2)，其中n是给定数列的长度。

以下是一个时间复杂度为O(n)的算法实现，称为“线性选择算法”。该算法的基本思路是每次将数列分成若干个大小为5的子数列，然后对每个子数列进行排序，取出每个子数列的中位数，再将这些中位数组成一个新的数列，重复以上过程，直到只剩下一个数，这个数就是所求的第k大的数。该算法的时间复杂度为O(n)。

以下是C++代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int linear_select(vector<int>& nums, int k) {
    if (k < 1 || k > nums.size()) {
        return -1; // 输入的 k 不合法，返回 -1 表示查找失败
    }
    int n = nums.size();
    vector<int> medians;
    for (int i = 0; i < n / 5; i++) {
        sort(nums.begin() + i * 5, nums.begin() + i * 5 + 5);
        medians.push_back(nums[i * 5 + 2]);
    }
    if (n % 5 != 0) {
        sort(nums.begin() + n / 5 * 5, nums.end());
        medians.push_back(nums[n / 5 * 5 + (n % 5 - 1) / 2]);
    }
    int median = medians.size() == 1 ? medians[0] : linear_select(medians, medians.size() / 2);
    vector<int> left, right;
    for (int i = 0; i < n; i++) {
        if (nums[i] < median) {
            left.push_back(nums[i]);
        } else if (nums[i] > median) {
            right.push_back(nums[i]);
        }
    }
    if (k <= right.size()) {
        return linear_select(right, k);
    } else if (k == right.size() + 1) {
        return median;
    } else {
        return linear_select(left, k - right.size() - 1);
    }
}

int main() {
    vector<int> nums = {3, 6, 9, 2, 8, 5};
    int k = 2;
    int res = linear_select(nums, k);
    if (res == -1) {
        cout << "输入的 k 不合法！" << endl;
    } else {
        cout << "第 " << k << " 大的数是：" << res << endl;
    }
    return 0;
}