给定一个数组，统计前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，则直接将数加入堆中；否则，如果该数比堆顶元素大，则将堆顶元素弹出，并将该数加入堆中。最后返回堆中的元素，按照从大到小的顺序排序即可。

相关问题

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序数对。一个排列中的逆序的总数就称为这个排列的逆序数。现在给定一个数组，求统计出该数组的逆序数对个数。用C++实现

可以使用归并排序的思想来解决这个问题，在归并排序的过程中统计逆序数对的个数。

具体思路如下：

1.将数组分成左右两部分，分别进行递归调用。

2.在递归到最小子问题时（即只有一个元素），直接返回。

3.在归并的过程中，比较左右两部分的元素大小，并将较小的元素存入临时数组中。若当前左部分元素较大，则逆序数对个数为右部分当前位置到结尾的元素个数。

4.将临时数组中的元素复制回原数组中。

5.返回逆序数对个数。

代码如下：

#include<iostream>
using namespace std;

int merge(int* nums, int left, int mid, int right)
{
    int i = left, j = mid + 1, k = 0;
    int* tmp = new int[right - left + 1];
    int cnt = 0;
    while (i <= mid && j <= right)
    {
        if (nums[i] <= nums[j]) tmp[k++] = nums[i++];
        else
        {
            tmp[k++] = nums[j++];
            cnt += mid - i + 1;
        }
    }
    while (i <= mid) tmp[k++] = nums[i++];
    while (j <= right) tmp[k++] = nums[j++];
    for (int p = 0; p < k; p++) nums[left + p] = tmp[p];
    delete[] tmp;
    return cnt;
}

int merge_sort(int* nums, int left, int right)
{
    if (left >= right) return 0;
    int mid = (left + right) / 2;
    int cnt = 0;
    cnt += merge_sort(nums, left, mid);
    cnt += merge_sort(nums, mid + 1, right);
    cnt += merge(nums, left, mid, right);
    return cnt;
}

int main()
{
    int nums[] = { 2, 4, 3, 1, 5, 6 };
    int cnt = merge_sort(nums, 0, 5);
    cout << cnt << endl; // 输出3
    return 0;
}

给定一个k位整数N，请编写程序统计每种不同的个位数字出现的次数，用C++的暴力枚举法

可以使用一个数组来记录每种不同的个位数字出现的次数，数组的下标代表个位数字，数组的值代表出现的次数。具体实现如下：

#include <iostream>
using namespace std;

int main() {
    int k;
    cin >> k;
    int count[10] = {0}; // 数组初始化为0
    while (k--) {
        int n;
        cin >> n;
        int digit = n % 10; // 获取个位数字
        count[digit]++; // 对应个位数字的计数器加1
    }
    for (int i = 0; i < 10; i++) {
        cout << i << ":" << count[i] << endl; // 输出每种个位数字出现的次数
    }
    return 0;
}

这个程序的时间复杂度为O(k)，可以通过本题。