Problem Description 输入一段序列，找出序列中第i小的数。 Input Description 第一行输入一个整数n（0<n<10000000）和一个整数i（1<=i<=n）。 第二行输入n个整数。 Output Description 输出第i小的整数。 Sample Input 10 5 1 2 3 4 5 6 7 8 9 10 Sample Output 5

这道题可以使用快速选择（Quick Select）算法来解决。快速选择算法是快速排序（Quick Sort）算法的变种，它的目标不是对整个序列进行排序，而是找出第k小的数。

快速选择算法的思路如下：

1. 随机选择一个数pivot，将序列分成两个部分：左边的数都小于pivot，右边的数都大于pivot。

2. 如果pivot是序列中的第k小的数，那么直接返回pivot；否则，如果pivot是序列中的第i小的数，那么返回pivot左边的数中的第i小的数；否则，返回pivot右边的数中的第i-k小的数。

3. 对左边或右边的序列重复以上步骤，直到找到第i小的数为止。

下面是Python实现代码：

相关问题

用C语言写Problem Description 已知N=12个事件的发生时刻和结束时刻（下表，并已按结束时刻升序排序）。一些在时间上没有重叠的事件可以构成一个事件序列，如{2,8,10}，事件序列包含的事件数目，称为该事件序列的长度。编程找出一个最长的事件序列。 Input Description 第一行输入一个整数0<N<1000，表示事件的数量。 接下来输入N行，输入两个数begin[i]，end[i]，分别表示时间的发生时刻与结束时刻，0<=i<N。 Output Description 输出最长的时间序列。 Sample Input 12 1 3 3 4 0 7 3 8 2 9 5 10 6 12 4 14 10 15 8 18 15 19 15 20 Sample Output {0,1,5,8,10}

以下是C语言的实现：

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

#define MAX_N 1000

struct event {
    int begin;
    int end;
};

int cmp(const void *a, const void *b) {
    return ((struct event *)a)->end - ((struct event *)b)->end;
}

int main() {
    int n, i, last_end = -1, len = 0;
    struct event events[MAX_N];
    int result[MAX_N];

    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        scanf("%d %d", &events[i].begin, &events[i].end);
    }

    qsort(events, n, sizeof(struct event), cmp);

    for (i = 0; i < n; i++) {
        if (events[i].begin >= last_end) {
            result[len++] = i;
            last_end = events[i].end;
        }
    }

    printf("{");
    for (i = 0; i < len; i++) {
        printf("%d", result[i]);
        if (i < len - 1) {
            printf(",");
        }
    }
    printf("}");

    return 0;
}

首先，我们定义了一个结构体event来存储每个事件的开始时间和结束时间。

然后，我们使用标准库函数qsort对所有事件按照结束时间升序排序。

接着，我们遍历所有事件，对于每个事件，如果其开始时间大于等于last_end，则将其加入到result中，并更新last_end为该事件的结束时间。

最后，我们输出result即为最长的事件序列。

注意，由于题目要求输出的是事件的下标，因此result中存储的是事件的下标，而不是开始时间或结束时间。

Problem Description 第一行1个*，第二行3个*...第n行2n-1个* Input 正整数n<100 Output n行，构成一个三角形c

算法思路：使用两层循环，外层循环控制行数，内层循环控制每一行输出的"*"个数。

Python 代码：

n = int(input()) # 输入正整数n
for i in range(1, n+1): # 外层循环控制行数
for j in range(1, 2*i): # 内层循环控制每一行输出的"*"个数
print("*", end="")
print() # 换行输出