p1923 求第 k 小的数 java

题目描述

给定一个长度为 n 的数列，求这个数列中第 k 小的数。

输入格式

第一行包含两个整数 n 和 k。

第二行包含 n 个整数（所有整数均在 1∼10^9 范围内），表示整个数列。

输出格式

输出一个整数，表示数列的第 k 小数。

数据范围

1≤n≤100000,

1≤k≤n

输入样例：

5 3
1 3 5 7 9

输出样例：

5

算法1

(快速选择) $O(n)$

时间复杂度

参考文献

python3 代码

C++ 代码

java 代码

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

相关问题

p1996 约瑟夫问题java

约瑟夫问题是一个数学应用问题，描述了n个人围坐在一张圆桌周围，从编号为k的人开始报数，每报到m的人出列，然后下一个人从1开始重新报数，直到所有人都出列为止。

在这个Java代码中，首先通过Scanner类获取输入的总人数n和报数的间隔m。然后使用LinkedList类创建一个链表sites，并依次将人的编号加入链表中。接下来，通过一个循环来模拟约瑟夫环的过程。在每一轮循环中，根据规则判断是移动链表的头结点还是将头结点移除并输出。当链表为空时，表示所有人都已经出列，循环结束。

P1678 烦恼的高考志愿java

这是一道算法题，需要使用贪心算法来解决。具体思路是先将所有学校按照录取分数线从高到低排序，然后从高到低依次填报志愿，直到填满为止。如果当前学校的录取分数线高于当前考生的分数，则跳过该学校，继续向下填报。如果所有学校都无法填报，则输出 "Impossible"。

Java代码实现如下：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 考生人数
        int m = scanner.nextInt(); // 学校个数
        int k = scanner.nextInt(); // 每个考生填报的志愿数

        List<Integer>[] schools = new List[m + 1];
        for (int i = 1; i <= m; i++) {
            schools[i] = new ArrayList<>();
            schools[i].add(scanner.nextInt()); // 录取分数线
            schools[i].add(i); // 学校编号
        }

        int[] choices = new int[n + 1]; // 记录每个考生填报的志愿
        for (int i = 1; i <= n; i++) {
            int score = scanner.nextInt();
            for (int j = 1; j <= k; j++) {
                int choice = scanner.nextInt();
                if (schools[choice].get(0) > score) { // 录取分数线高于考生分数，跳过该学校
                    continue;
                }
                choices[i] = choice;
                schools[choice].add(i); // 将考生加入该学校的候选名单中
                break;
            }
        }

        for (int i = 1; i <= m; i++) {
            Collections.sort(schools[i], Collections.reverseOrder()); // 将每个学校的候选名单按照分数从高到低排序
            schools[i].remove(0); // 删除录取分数线
            for (int j = 0; j < schools[i].size(); j++) {
                System.out.print(schools[i].get(j) + " ");
            }
            System.out.println();
        }

        scanner.close();
    }
}