topk()--获得K个数-确认其比k+1之后的数都大即可，不对这k个数进行排序。伪代码

假设有一个列表 nums，要求获得其中前 k 个最大的数，可以使用如下的伪代码：

# 初始化前 k 个数
top_k = nums[:k]

# 遍历剩余的数
for num in nums[k:]:
    # 如果当前数比前 k 个数中最小的数还小，则跳过
    if num < min(top_k):
        continue
    # 否则，将当前数加入前 k 个数中，并且去掉最小的数
    top_k.remove(min(top_k))
    top_k.append(num)

# 最后返回前 k 个数
return top_k

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

相关问题

求解中位数的c语言算法,BFPRT 算法（TOP-K 问题）

BFPRT算法是一种解决Top-K问题的算法，其中K为要找的第K大的元素。该算法的时间复杂度为O(n)。

BFPRT算法的基本思想是通过划分算法来找到中位数，然后根据中位数将数组分成两部分，只需要在一部分中查找Top-K，另一部分不用查找。

以下是BFPRT算法的c语言实现：

#include <stdio.h>
#include <stdlib.h>

#define SWAP(a, b) {int temp = a; a = b; b = temp;}

// 求中位数
int median(int arr[], int left, int right) {
    int center = (left + right) / 2;
    if (arr[left] > arr[center]) SWAP(arr[left], arr[center])
    if (arr[left] > arr[right]) SWAP(arr[left], arr[right])
    if (arr[center] > arr[right]) SWAP(arr[center], arr[right])
    SWAP(arr[center], arr[right - 1])
    return arr[right - 1];
}

// 划分函数
int partition(int arr[], int left, int right, int pivot) {
    int i, j;
    for (i = left, j = right - 2;;) {
        while (arr[++i] < pivot);
        while (arr[--j] > pivot);
        if (i < j) SWAP(arr[i], arr[j])
        else break;
    }
    SWAP(arr[i], arr[right - 1])
    return i;
}

// BFPRT算法
int bfprt(int arr[], int left, int right, int k) {
    if (left + 1 == right) return arr[left];
    int pivot = median(arr, left, right);
    int mid = partition(arr, left, right, pivot);
    int num = mid - left + 1;
    if (k == num) return arr[mid];
    else if (k < num) return bfprt(arr, left, mid, k);
    else return bfprt(arr, mid + 1, right, k - num);
}

int main() {
    int arr[] = {3, 4, 2, 1, 5, 6, 8, 7, 9};
    int len = sizeof(arr) / sizeof(int);
    int k = 5;
    int kth = bfprt(arr, 0, len, k);
    printf("The %dth number is: %d\n", k, kth);
    return 0;
}

该算法的核心是BFPRT划分算法，该算法是一个递归算法，每次递归的时间复杂度为O(n)，因此总的时间复杂度为O(nlogn)。

给定一个数组，统计前k大的数并且把这k个数从大到小输出。

可以使用堆排序来解决这个问题。首先建立一个大小为k的小根堆，遍历数组，将每个数与堆顶元素比较，如果比堆顶元素大，则将堆顶元素替换为该数，并重新调整堆。最终堆中的k个元素就是前k大的数，将它们从大到小输出即可。

具体实现可以参考以下代码：

import heapq

def top_k(nums, k):
    heap = []
    for num in nums:
        if len(heap) < k:
            heapq.heappush(heap, num)
        elif num > heap[]:
            heapq.heappushpop(heap, num)
    return sorted(heap, reverse=True)

nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
k = 3
print(top_k(nums, k))  # [9, 6, 5]

这里使用了Python内置的heapq模块来实现堆排序。首先建立一个空堆，然后遍历数组，如果堆的大小小于k，则直接将数加入堆中；否则，如果该数比堆顶元素大，则将堆顶元素弹出，并将该数加入堆中。最后返回堆中的元素，按照从大到小的顺序排序即可。