题面描述

给定一个长度为$n$的数组$a$下标从$1$开始对于所有$i∈[1,n]∩Z$，求出区间 $[1, i]$ 中第$k$小的数。其中$k$为给定常数。如果区间内的数的数量不足$k$个，请输出$-1$。

思路

1. 使用最大堆 为了高效地求出每个前缀区间 $[1, i]$ 的第 $k$ 小的数，我们可以使用最大堆来动态维护前 $k$ 小的元素。

最大堆：最大堆的特性是堆顶元素是堆中最大的元素。我们通过维护一个大小为 $k$ 的最大堆，可以确保堆中保存的是当前区间的前 $k$ 小的元素，而堆顶即为该区间的第 $k$ 小元素。

2. 具体实现步骤

插入元素到堆：对于每个元素 $a[i]$，我们将其插入到最大堆中。此时堆中可能有超过 $k$ 个元素。

维护堆的大小：当堆中的元素超过 $k$ 个时，我们弹出堆顶元素（即当前最大的元素）。这样堆中的元素始终保持为前 $k$ 小的元素。

输出结果：在遍历每个前缀时，如果当前前缀长度不足 $k$，输出 -1；如果前缀长度大于等于 $k$，输出最大堆的堆顶元素（即第 $k$ 小的数）。

3. 处理边界情况

如果当前前缀长度小于 $k$，直接输出 -1。 当前缀长度大于等于 $k$ 时，输出最大堆的堆顶元素。

代码说明

代码说明（通用语言）

1.输入处理：

首先读取输入，包括数组长度 n 和所需的第 k 小的元素 k。 然后读取数组 a 的元素。数组的长度为 n，每个元素都被存储在一个列表或数组结构中。

2.最大堆的使用：

我们使用一个最大堆（通常用 priority_queue 实现）来动态维护当前区间内的前 k 小的元素。最大堆的特点是堆顶始终是当前堆中最大的元素。 对于每个元素 a[i]，将其插入到最大堆中。 当堆的大小超过 k 时，我们从堆中弹出堆顶元素，即最大的那个元素。这样可以确保堆中只保留当前区间中最小的 k 个元素。

3.结果输出：

对于每个元素 a[i]： 如果当前区间的长度（即 i + 1）小于 k，则输出 -1，因为区间中的元素数量不足 k。 如果当前区间的长度大于或等于 k，则输出最大堆的堆顶元素。堆顶元素即为当前区间中的第 k 小的元素。 将每个 i 的结果存储在一个列表或数组中，最后按要求输出结果。

4.时间复杂度分析：

对于每个元素插入堆的操作，时间复杂度为 O(log k)，因为堆的大小不会超过 k。 在数组遍历过程中，总共有 n 个元素，因此总的时间复杂度为 O(n log k)，其中 n 是数组的长度，k 是需要找的第 k 小的元素。

cpp

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

int main() {
    int n, k;
    cin >> n >> k;  // 输入数组长度n 和 第k小的数

    vector<int> a(n);  // 存储数组
    for (int i = 0; i < n; ++i) {
        cin >> a[i];  // 读取数组元素
    }

    // 定义最大堆，使用 priority_queue 实现
    // 最大堆用于保存当前区间前 k 小的元素
    priority_queue<int> max_heap;

    vector<int> result(n);  // 存储每个 i 的结果
    
    // 遍历数组，动态维护区间 [1, i] 中的第 k 小数
    for (int i = 0; i < n; ++i) {
        max_heap.push(a[i]);  // 将当前元素插入最大堆

        // 如果最大堆中的元素超过 k 个，弹出堆顶元素（即最大元素）
        if (max_heap.size() > k) {
            max_heap.pop();
        }

        // 当 i < k-1 时，区间 [1, i] 的元素数量不足 k，输出 -1
        if (i < k - 1) {
            result[i] = -1;
        } else {
            // 当 i >= k-1 时，堆顶元素即为区间 [1, i] 中的第 k 小元素
            result[i] = max_heap.top();
        }
    }

    // 输出结果
    for (int i = 0; i < n; ++i) {
        if (i > 0) cout << " ";  // 输出时用空格分隔结果
        cout << result[i];
    }
    cout << endl;

    return 0;
}

python

import heapq

def find_kth_smallest(n, k, arr):
    max_heap = []  # 最大堆，用于保存当前区间前 k 小的元素
    result = []  # 存储每个前缀的结果

    for i in range(n):
        heapq.heappush(max_heap, -arr[i])  # 插入元素时取相反数，模拟最大堆

        # 如果最大堆中的元素超过 k 个，弹出堆顶元素（即最大元素）
        if len(max_heap) > k:
            heapq.heappop(max_heap)

        # 当 i < k-1 时，区间 [1, i] 的元素数量不足 k，输出 -1
        if i < k - 1:
            result.append(-1)
        else:
            # 堆顶元素即为区间 [1, i] 中的第 k 小元素，取反数恢复原值
            result.append(-max_heap[0])

    return result

# 读取输入
n, k = map(int, input().split())
arr = list(map(int, input().split()))

# 获取结果
output = find_kth_smallest(n, k, arr)

# 输出结果
print(" ".join(map(str, output)))

java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();  // 读取数组长度 n
        int k = sc.nextInt();  // 读取第 k 小的数 k
        int[] a = new int[n];  // 存储数组元素
        
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();  // 读取数组元素
        }

        // 定义最大堆，优先队列实现
        // 最大堆用于保存当前区间前 k 小的元素
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        int[] result = new int[n];  // 存储每个前缀的结果
        
        // 遍历数组，动态维护区间 [1, i] 中的第 k 小数
        for (int i = 0; i < n; i++) {
            maxHeap.offer(a[i]);  // 将当前元素插入最大堆

            // 如果最大堆中的元素超过 k 个，弹出堆顶元素（即最大元素）
            if (maxHeap.size() > k) {
                maxHeap.poll();
            }

            // 当 i < k-1 时，区间 [1, i] 的元素数量不足 k，输出 -1
            if (i < k - 1) {
                result[i] = -1;
            } else {
                // 当 i >= k-1 时，堆顶元素即为区间 [1, i] 中的第 k 小元素
                result[i] = maxHeap.peek();
            }
        }

        // 输出结果
        for (int i = 0; i < n; i++) {
            if (i > 0) System.out.print(" ");  // 输出时用空格分隔结果
            System.out.print(result[i]);
        }
        System.out.println();  // 输出结束行
        
        sc.close();
    }
}

题目内容

给定一个长度为 $n$ 的数组 $a$ (下标从 $1$ 开始),对于所有 $i∈[1,n]∩Z$ ，求出区间 $[1,i]$ 中第 $k$ 小的数。其中 $k$ 为给定常数。

输入描述

第一行两个整数 $n,k(1<=k<n<=10^5)$ ,表示数组的长度及两个给定常数。

第二行 $n$ 个整数,第 $2$ 个整数为 $a_i$ 的值($1<=a_i<=n$,且 $a_i$ 互不相等)

输出描述

输出一行 $n$ 个数,第 $1$ 个数为区间 $[1,i]$ 中第 $k$ 小的数,以空格分隔。

若区间内的数的数量不足 $k$ 个,请输出 $-1$ 。

样例1

输入

5 2
5 4 3 2 1

输出

-1 5 4 3 2