首页 > 试题广场 >

查找第K小数

[编程题]查找第K小数
  • 热度指数:19909 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
查找一个数组的第K小的数,注意同样大小算一样大。 如  2 1 3 4 5 2 第三小数为3。

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


输出描述:
输出第k小的整数。
示例1

输入

6
2 1 3 5 2 2
3

输出

3
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        priority_queue<int, vector<int>, greater<int>> Q;
        int tmp;
        for(int i=0;i<n;i++){
            scanf("%d", &tmp);
            Q.push(tmp);
        }
        int k;
        scanf("%d", &k);
        tmp = Q.top();
        Q.pop();
        for(int i=2;i<=k;i++){
            while(tmp==Q.top())
                Q.pop();
            tmp = Q.top();
            Q.pop();
        }
        printf("%d\n", tmp);
    }
}


发表于 2018-03-19 15:32:09 回复(3)

python两行解法:

要注意去重。

while True:
    try:
        a,b,c=int(input()),map(int,input().split()),int(input())
        print(sorted(set(b))[c-1])

    except:
        break
发表于 2017-10-01 15:01:19 回复(3)
#include<bits/stdc++.h>
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        int a[10000]={0},k=0;
        for(int i=0;i<n;i++){
            scanf("%d",&k);
            a[k]++;
        }
        scanf("%d",&k);
        int s=0;
        for(int i=0;i<10000;i++){
            if(a[i]>0) s++;
            if(s==k){
                s=i;
                break;
            }
        }
        printf("%d\n",s);
    }
}//hash法,也可用堆
编辑于 2019-03-19 15:07:04 回复(1)
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main
{
    public static Set<Integer> set;
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        set = new HashSet<>();
        for(int i = 0; i < n; i++)
            set.add(scan.nextInt());
        Object[] converted = set.toArray();
        Arrays.sort(converted);
        System.out.println(converted[scan.nextInt() - 1]);
        
        scan.close();
    }
    
}

发表于 2018-07-26 21:45:40 回复(0)

map的键会自动按序排列。

#include <iostream>
#include <map>
using namespace std;
int main()
{
    int n,i,k,tmp;
    while(cin>>n)
    {
        map<int,int> mmap;
        for(i=0;i<n;++i)
        {
            cin>>tmp;
            mmap[tmp]=1;
        }
        cin>>k;
        auto it=mmap.begin();
        for(;it!=mmap.end()&&k!=1;++it,--k){}
        cout << it->first << endl;
    }
    return 0;
}
发表于 2019-04-29 14:58:52 回复(2)

运行时间:44ms
占用内存:10932k
思路、注释,在代码里了。

import java.util.Arrays;
import java.util.Scanner;
/**
 * @author Allen_Hua
 * @create_time 创建时间:May 11, 2018 9:24:25 PM 类说明
 */
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            int n = scan.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = scan.nextInt();
            }
            int k = scan.nextInt();// 第k小的数
            // 从小到大排了序
            Arrays.sort(arr);
            // 遇到一种新的元素就加一 默认arr[0]是一种元素 temp初始化值为1
            int temp = 1;
            for (int i = 1; i < arr.length; i++) {
                // 如果该数和前面一个数一样 则continue 
                // 不会执行循环体内该句下面的代码
                if (arr[i] == arr[i - 1]) {
                    continue;
                } else {// 如果该数和前面一个数不一样 则遇到了新的数
                    temp++;
                }
                if (temp == k) {
                    System.out.println(arr[i]);
                }
            }
        }
    }
}
编辑于 2018-05-11 21:50:25 回复(1)
//复杂度o(nlogn),先排序,然后相等的不输入,不等的计数加一,直到第k个不等的
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(cin>>n){
        int *a=new int[n],k,pos=1;
        for(int i=0;i<n;i++)
            cin>>a[i];
        sort(a,a+n);
        cin>>k;
        if(k==1)
            cout<<a[0];
        else{
            for(int i=1;i<n;i++){
                if(a[i]!=a[i-1])
                    pos++;
                if(pos==k){
                    cout<<a[i]<<endl;
                    break;
                }
            }
        }
    }
    return 0;
}

发表于 2020-01-14 15:05:20 回复(2)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(void)
{
    int n;
    vector<int> a;
    
    while(cin >> n)
    {
        for(int i = 0;i < n;i++)
        {
            int x;
            cin >> x;
            a.push_back(x);
        }
        
        int k;
        cin >> k;
        
        sort(a.begin(),a.end());
        
        int count = 0;//用来记数第K小的数
        int max = 0;
        
        for(vector<int>::iterator it = a.begin();it != a.end();it++)
        {
            if(*it > max)
            {
                max = *it;
                count++;
            }
            if(count == k)
                break;
        }
        cout << max << endl;
    }
    return 0;
}

编辑于 2021-02-14 16:06:17 回复(0)
#include<iostream>
//#include<map>//map插入与搜索均是对数时间
#include<queue>//priority_queue查找最大值常数时间,插入对数时间
using namespace std;
int main()
{
	int n, k, x;
	while (cin>>n)
	{
		priority_queue<int, vector<int>, greater<int>> PQ;
		for (int i = 0; i < n; i++)
		{
			cin >> x;
			PQ.push(x);
		}
		cin >> k;
		x = PQ.top();
		PQ.pop();
		for (int i = 0; i < k - 1; i++)
		{
			if (PQ.size() > 0)//防止没有第K小的数
			{
				if (PQ.top() == x)
					i--;
				else
					x = PQ.top();
				PQ.pop();
			}
			else
				break;
		}
		cout << x << endl;
	}
	return 0;
}

小根堆,或者叫优先队列,插入O(logn),查找O(1)
而map由红黑树实现,插入O(logn),查找O(logn)
编辑于 2020-06-24 13:57:41 回复(0)
#include<stdio.h>
int a[1000],n;
int min()
{
    int min=a[0],i,j;
    for(i=1;i<n;i++)//找到最小的值
        if(a[i]<min)
            min=a[i];
    for(i=0;i<n;i++)//去重
        if(a[i]==min)
        {
            for(j=i;j<n-1;j++)
                a[j]=a[j+1];//循环前移
            n--;
            i--;
        }
    return min;
}
int main()
{
    int m,i,key;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    scanf("%d",&m);
    while(m--)
        key=min();
    printf("%d",key);
}

发表于 2020-05-06 14:47:29 回复(0)
思想:通过散列表去重复元素来顺序查找
#include<stdio.h>
bool flag[1000]={0};
int main(){
    int n,x,k,j;
    int cnt=0;
    scanf("%d",&n);
    int a[n];
    for(int i=0;i<n;i++){
        scanf("%d",&x);
        flag[x]=true;
        a[i]=x;
    }
    scanf("%d",&k);
    for(j=0;j<1000;j++){
        if(flag[j]==true){
            cnt++;
            if(cnt==k)
                break;
        }
    }
    printf("%d",j);
}


编辑于 2020-03-18 22:14:02 回复(0)
Java 解法, 使用TreeSet
import java.util.ArrayList;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        TreeSet<Integer> set = new TreeSet<>();
        int n = scanner.nextInt();
        for (int i = 0; i < n; i++) set.add(scanner.nextInt());
        ArrayList<Integer> list = new ArrayList<>(set);
        int k = scanner.nextInt();
        System.out.println(list.get(k-1));
    }
}


发表于 2020-03-18 13:02:29 回复(0)
import java.util.Arrays;
import java.util.Scanner;

public class Main{
	
	public static void main(String[] args)  {
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext()) {
			int n = scanner.nextInt();
			int[] nums = new int[n];
			for(int i = 0; i < n; i++) {
				nums[i] = scanner.nextInt();
			}
			int min = scanner.nextInt();
			Arrays.sort(nums);
			for(int i = 1; i < nums.length; i++) {
				if(nums[i] == nums[i - 1]) continue;
				min--;
				if(min == 1) {
					System.out.println(nums[i]);
					return;
				}
			}
		}
	}
}

发表于 2020-03-08 20:48:40 回复(0)
//思路:利用set元素不重复的特性寻找第k小元素
//时间复杂度:O(nlogn)
#include<stdio.h>
#include<iostream>
#include<vector>
#include<set>
#include<iterator>
int main(){
    int n=-1,data=-1,seq=-1;
    std::vector<int> input;
    int count=0;
    int temp=-1;
    //std::set<int> result;
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++){
            std::cin>>data;
            input.push_back(data);
        }
        std::set<int> result(input.begin(),input.end());
        std::cin>>seq;
        for(std::set<int>::iterator it=result.begin();it!=result.end();it++,count++){
            if(count==seq-1){
                temp=*it;
                break;
            }
        }
        std::cout<<temp<<std::endl;
        result.clear();
        input.clear();
    }
}
发表于 2020-02-20 15:47:07 回复(0)
这题可以不用排序,直接查找第k个最小的数,时间复杂o(n^2)。
#include <stdio.h>
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        int a[n],seq,min;
        for(int i=0;i<n;i++)scanf("%d",&a[i]);
        scanf("%d",&seq);
        for(int i=0;i<seq;i++)                  //进行seq次最小查找;
        {
            min=a[0];
            for(int j=1;j<n;j++)if(min>a[j])min=a[j]; //查找当前序列最小值
            for(int j=0;j<n && i!=seq-1;j++)    //去重,当前最小值用尾部的值替换
            {                               //最后一次查找不去重,因为没有意义
                if(min==a[j])
                {
                    while(a[n-1]==min && n-1>j)n--;  //注意数组末尾的数可能等于当前最小值!
                    a[j]=a[n-1];
                    n--;
                }
            }
        }
        printf("%d\n",min);
    }
}


编辑于 2020-03-18 09:54:15 回复(3)
#include<stdio.h>
#include<algorithm>
using namespace std;
int buf[1001];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%d",&buf[i]);
        }
        sort(buf,buf+n);
        int k;
        scanf("%d",&k);
        int count=1;//注意这里
        int x=buf[0];
        for(int i=1;count<k&&i<n;i++)
        {
            if(x<buf[i])
            {
                count++;
                x=buf[i];
            }
        }
        printf("%d\n",x);
    }
    return 0;
}

发表于 2019-02-27 17:46:44 回复(0)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//hash T(n)=O(n)
int main()
{
    int a[1000],n,i,x,count,y;
    while(scanf("%d",&n)!=EOF){
        memset(a,0,sizeof(a));
        for(i=0;i<n;i++){
            scanf("%d",&x);
            a[x]=1;
        }
        scanf("%d",&y);
        count=0;i=0;
        while(count!=y){
            if(a[i]!=0)
                count++;
            i++;
        }
        printf("%d\n",i-1);
    }
} 

发表于 2019-02-21 23:28:47 回复(0)
去重O(n), 排序O(nlogn),总时间复杂度O(nlogn)
#include <stdio.h>
#define maxn 1005
int n,k;
int a[maxn];
void DelRepeat(int *a,int n){
    int i,j;
    for(i=0,j=1;j<n;j++){
        if(a[i]!=a[j])
            a[++i]=a[j];
    }
}
int Partition(int *a,int left,int right){
    int pivot=a[left];
    while(left<right){
        while(left<right && a[right]>=pivot)
            right--;
        a[left]=a[right];
        while(left<right && a[left]<=pivot)
            left++;
        a[right]=a[left];
    }
    a[left]=pivot;
    return left;
}
void QuickSort(int *a,int left,int right){
    int pivotpos;
    if(left<right){
        pivotpos=Partition(a,left,right);
        QuickSort(a,left,pivotpos-1);
        QuickSort(a,pivotpos+1,right);
    }
}
int main(){
    int i;
    while(scanf("%d",&n)!=EOF){
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        scanf("%d",&k);
        QuickSort(a,0,n-1);
        DelRepeat(a,n);
        printf("%d\n",a[k-1]);
    }
    return 0;
}


发表于 2019-01-09 19:18:57 回复(0)
import java.util.*;
public  class Main{
    public static void main(String[] args){
        int n;
        int[] a=new int[1000];
        ArrayList<Integer> list=new ArrayList<Integer>();
        HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
        Scanner scanner=new Scanner(System.in);
        while(scanner.hasNext()){
            n=scanner.nextInt();
            for(int i=0;i<n;i++){
                a[i]=scanner.nextInt();
                if(!map.containsKey(a[i])){
                    map.put(a[i],1);
                    list.add(a[i]);
                }
            }
            Collections.sort(list);
            int k;
            k=scanner.nextInt();
            System.out.println(list.get(k-1));
        }
    }
} 

发表于 2018-09-13 20:47:38 回复(0)
#include<cstdio>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>

int compare(const void * a, const void * b) {
    return *(int *)a > *(int *)b;
}

int main() {
    int count;
    while (scanf("%d", &count) != EOF) {
        int vec[1000] = {};
        for (int i = 0; i < count; i++) {
            scanf("%d", &vec[i]);
        }
        int k;
        scanf("%d",&k);
        qsort(vec, count, sizeof(int), compare);
        for (int i = 0; i < count - 1; i++) {
            if (vec[i] != vec[i + 1])
                k--;
            if (k == 0)
                printf("%d\n",vec[i]);
        }
    }
}
发表于 2018-02-08 16:47:19 回复(0)