第X大的数

柔光的暖阳◎ 2022-06-17 05:28 121阅读 0赞

#### Problem Description ####

X最近爱上了区间查询问题，给出N (N <= 100000) 个数，然后进行M (M <= 5) 次询问，每次询问时，输入一个数X (1 <= X <= N)，输出N个数中第X大的数。

#### Input ####

多组输入。

每组首先输入一个整数N，代表有N个数，下面一行包含N个整数，用空格隔开。然后为一个整数M，代表有M次询问，下面的M行，每行一个整数X。

#### Output ####

输出N个数中第X大的数。

#### Example Input ####

4
    1 2 2 3
    4
    1
    2
    3
    4

#### Example Output ####

3
    2
    2
     1 #include<stdio.h>
    int find(int k,int left,int right,int a[])
    {
        int i,j,mid;
        i=left;
        j=right;
        mid=a[i];
        while(i<j)
        {
            while(i<j&&a[j]<=mid)
            {
                j--;
            }
            a[i]=a[j];
            while(i<j&&a[i]>=mid)
            {
                i++;
            }
            a[j]=a[i];
        }
        a[i]=mid;
        if(i==k)
        {
            return a[i];
        }
        else if(i<k)
        {
            find(k,j+1,right,a);
        }
        else
        {
            find(k,left,j-1,a);
        }
    }
    int main()
    {
        int i,k,n,m;
        int a[10000];
        int b;
        while(scanf("%d",&n)!=EOF)
        {
            for(i=0;i<n;i++)
            {
                scanf("%d",&a[i]);
            }
            scanf("%d",&m);
            while(m--)
            {
                scanf("%d",&k);
                b=find(k-1,0,n-1,a);
                printf("%d\n",b);
            }
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，121人围观）

还没有评论，来说两句吧...

相关阅读

相关 1255: 寻找最大数X

1255: 寻找最大数X 时间限制: 1 Sec 内存限制: 128 MB 提交: 79 解决: 56 您该题的状态：已完成 \[[提交][Link 1

妖狐艹你老母/ 2024年02月18日 22:04/ 0 赞/ 39 阅读

相关数组中第K大的数

题目描述有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存

迈不过友情╰/ 2022年12月21日 04:51/ 0 赞/ 191 阅读

相关 11-06 第三大的数

[原题链接][Link 1] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6

素颜马尾好姑娘i/ 2022年12月19日 11:42/ 0 赞/ 159 阅读

相关寻找第 K 大的数

寻找第 K 大的数 1、参考资料 https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

爱被打了一巴掌/ 2022年12月05日 04:51/ 0 赞/ 222 阅读

相关（力扣）第414. 第三大的数

414. 第三大的数 -------------------- 题目要求：给你一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。 -

蔚落/ 2022年11月12日 09:33/ 0 赞/ 163 阅读

相关算法题目——第K大的数

题目链接：[剑指offer.76][offer.76] 思路：使用 priority\_queue 构建优先队列，这里注意要构建大顶堆，使less； pop() 弹

Myth丶恋晨/ 2022年09月15日 12:45/ 0 赞/ 159 阅读

相关第X大的数

第X大的数 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [ Statistic][

亦凉/ 2022年07月03日 14:55/ 0 赞/ 136 阅读

相关第X大的数

Problem Description X最近爱上了区间查询问题，给出N (N <= 100000) 个数，然后进行M (M <= 5) 次询问，每次询问时，输入一个数X

柔光的暖阳◎/ 2022年06月17日 05:28/ 0 赞/ 122 阅读

相关 LeetCode414. 第三大的数

给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。示例 1: 输入: [3, 2, 1]

雨点打透心脏的1/2处/ 2022年05月23日 07:35/ 0 赞/ 218 阅读

相关寻找第K大的数

1，对于一个有序数组则为第K个数，O（1） 2，对于一个无序数组使用修改的快排划分算法，时间复杂度为O（n） 3，对于两个无序数组

小咪咪/ 2022年05月21日 03:20/ 0 赞/ 193 阅读