首页 > ACM题库 > 九度OJ > 九度-1174-查找第K小数[解题代码]
2013
12-13

九度-1174-查找第K小数[解题代码]

题目来源:2010年北京邮电大学网院研究生机试真题

题目描述:

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

输入:

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

输出:

输出第k小的整数。

样例输入:
6
2 1 3 5 2 2
3
样例输出:
3

java 代码如下:
import java.util.Scanner;
import java.util.TreeSet;


public class Main {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		while(s.hasNextInt()){
			TreeSet<Integer> set = new TreeSet<Integer>();
			int n = s.nextInt();
			Object[] arr = new Object[n];
			for(int i=0; i<n; i++){
				set.add(s.nextInt());
			}
			int k = s.nextInt();
			arr = set.toArray();
			System.out.println(arr[k-1]);
		}
	}

}

/**************************************************************
	Problem: 1174
	User: coder
	Language: Java
	Result: Accepted
	Time:340 ms
	Memory:20260 kb
****************************************************************/


  1. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.

  2. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  3. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。