第k极值（C/C++）+ 常见误区

解题思路:
                    题前小磕：这一题一看题目就非常简单，但是为什么我还要写这个题解呢？这个代码改了好久....因为淋过雨，所以要帮你们撑伞！！！（好久没有写题解了，更新一下）

                    大致思路：

                    题目要求求出整个序列中第k大的数字减去第k小的数字的值m，并判断m是否为质数。一看第k大、第k小就知道必须要先排序。其次要知道第k大的数字和第k小的数字对应的下标是多少，第k小的数字下标是 k-1,第k大的下标是 n - k。如果不知道为什么的，建议回去复习一下数组（提示：下标）。这样就能得到需要判断的那个数了（暂时把这个数叫res）。接下来就是判断质数了。这里注意一个细节，就是质数的定义：质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。（必须大于1）。而质数的判断方法有好几种，能相信做到这道题的应该都会吧！本题解使用的是优化的暴力筛选法（sqrt函数），如果不懂，就去百度一下吧！！！

                    具体步骤：

                                    1、排序（使用C语言的同学可以使用冒泡排序法或者快速排序法、C++的同学使用标准库函数sort即可，注意要使用algorithm头文件）

                                    2、得到需要进行判断的数字res。res = nums[n - k] - nums[k - 1]

                                    3、判断是否为质数

注意事项：

                    1、排序如果使用冒泡排序法或者快速排序法，要注意边界范围，小心越界。（如果不会排序的，可以看我之前写的关于排序的题解，超级详细）

                    2、在进行质数判断前一定要判断那个数是否大于1（我就是因为，才没有通过）

                    3、质数判断时，要注意循环条件为i <= (int)sqrt(res)，以防49这样的数字判断成质数

参考代码:

C++代码

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 10000;
int nums[N];

bool isprime(int x)
{
    if(x <= 1)//紧扣质数定义 如果小于等于1，直接返回false
        return false;
    else
    {
        int flag = 1;
        for(int i = 2;i <= (int)sqrt(x);i++)
        {
            if(x % i == 0)
                flag = 0;
        }
        if(flag == 1)
            return true;
        else
            return false;
    }
}

int main()
{
    int n,k;
    cin >> n >> k;
    for(int i = 0;i < n;i++)
        cin >> nums[i];

    sort(nums,nums + n);//进行排序，不要忘了头文件algorithm
    int res = nums[n - k] - nums[k - 1];//得到需要进行判断的数字

    if(isprime(res))//进行质数判断
    {
        cout << "YES" << endl;
        cout << res << endl;
    }
    else
    {
        cout << "NO" << endl;
        cout << res << endl;
    }
    return 0;
}

C代码

#include <stdio.h>
#include <math.h>

void quick_sort(int nums[],int l,int r)//快速排序法
{
    if(l >= r)
        return;
    int i = l - 1,j = r + 1,x = nums[(l + r) / 2];
    while(i < j)
    {
        do i++;while(nums[i] < x);
        do j--;while(nums[j] > x);
        if(i < j)
        {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
    }
    quick_sort(nums,l,j);
    quick_sort(nums,j + 1,r);
}

int isprime(int x)//质数判断
{
    if(x <= 1)//如果小于等于1，直接退出
        return 0;
    else
    {
        int flag = 1;
        for(int i = 2;i <= (int)sqrt(x);i++)
        {
            if(x % i == 0)
                flag = 0;
        }
        if(flag == 1)
            return 1;
        else
            return 0;
    }
}

int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    static int N = 10000;//防止数组太大，导致爆栈
    int nums[N];
    for(int i = 0;i < n;i++)
    {
        scanf("%d",&nums[i]);
    }
    quick_sort(nums,0,n - 1);//快速排序法
    int res = nums[n - k] - nums[k - 1];//得到需要进行判断的数
    if(isprime(res))
    {
        printf("YES\n");
        printf("%d\n",res);
    }
    else
    {
        printf("NO\n");
        printf("%d\n",res);
    }
    return 0;
}