【九度OJ】题目1174：查找第K小数 解题报告

标签（空格分隔）： 九度OJ

---

原题地址：http://ac.jobdu.com/problem.php?pid=1174

题目描述：

查找一个数组的第K小的数，注意同样大小算一样大。
如 2 1 3 4 5 2 第三小数为3。

输入：

输入有多组数据。
每组输入n，然后输入n个整数(1<=n<=1000)，再输入k。

输出：

输出第k小的整数。

样例输入：

6

2 1 3 5 2 2

3

样例输出：

3

Ways

又没有一遍A，是忘记写using namespace std;了。。

很简单题，要找第k小的数，首先想到排序，但是会有重复数字。我的第一想法是去重，后来感觉太麻烦，直接用temp保留上一次的数字，如果下一个数和上一个数是一样的就不count，如果不一样就更新count和temp。这样就很贱了。

#include<stdio.h>

#include<algorithm>

using namespace std;

int main() {

    int n, k;

    int ns[1001];

    while (scanf("%d", &n) != EOF) {

        for (int i = 0; i < n; i++) {

            scanf("%d", &ns[i]);

        }

        scanf("%d", &k);

        sort(ns, ns + n);

        int temp = 0;

        int count = 0;

        for (int i = 0; i < n; i++) {

            if (ns[i] != temp) {

                count++;

                temp = ns[i];

            }

            if (count == k) {

                printf("%d\n", temp);

                break;

            }

        }

    }

    return 0;

}

Date

2017 年 3 月 16 日