HDOJ 2561. 第二小整数 第k大问题

第二小整数

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 8299    Accepted Submission(s): 5227

Problem Description

求n个整数中倒数第二小的数。
每一个整数都独立看成一个数，比如，有三个数分别是1，1，3，那么，第二小的数就是1。

Input

输入包含多组测试数据。
输入的第一行是一个整数C，表示有C测试数据；
每组测试数据的第一行是一个整数n，表示本组测试数据有n个整数（2<=n<=10），接着一行是 n个整数 (每个数均小于100);

Output

请为每组测试数据输出第二小的整数，每组输出占一行。

Sample Input

2
2
1 2
3
1 1 3

Sample Output

2
1

Author

yifenfei

Source

绍兴托普信息技术职业技术学院——第二届电脑文化节程序设计竞赛

来源： <http://acm.hdu.edu.cn/showproblem.php?pid=2561>

        这是一个求第k大的类似问题，转化一下就是第k小。

        不过这个题目数据很小，就是拿来卖萌的，排个序就好了。

 #include <stdio.h>
 #include <algorithm>
 int main()
 {
     int C, n, arr[];
     scanf("%d", &C);
     while(C--) {
         scanf("%d", &n);
         for(int i=; i<n; i++)
             scanf("%d", arr+i);
         std::sort(arr, arr+n);
         printf("%d\n", arr[]);
     }
     return ;
 }

        不过下午上机实在无聊，于是手痒写了快排思想的第k小。

        有学过快排的都很容易理解了，partition把数组分成两份，如果k（也就是2）在左边区间就对左边区间求第k小，或者在右边区间求。注意下标从0开始的话，k要减一下。

 #include <stdio.h>
 #include <algorithm>

 int partition(int *arr, int p, int q) {
     int pivot=arr[p];
     int i=p, j=q;
     while(i<j) {
         while(arr[j]>=pivot&&i<j)
             --j;
         arr[i]=arr[j];
         while(arr[i]<=pivot&&i<j)
             ++i;
         arr[j]=arr[i];
     }
     arr[i]=pivot;
     return i;
 }

 int KthMin(int *arr, int p, int q, int k) {
     int m=partition(arr, p, q);
     if(m<k-)
         return KthMin(arr, m+, q, k);
     else if(m>k-)
         return KthMin(arr, p, m-, k);
     else
         return arr[m];
 }

 int main()
 {
     int C, n, arr[];
     scanf("%d", &C);
     while(C--) {
         scanf("%d", &n);
         for(int i=; i<n; i++)
             scanf("%d", arr+i);
         printf("%d\n", KthMin(arr, , n-, ));
     }
     return ;
 }

By Black Storm（使用为知笔记）