买帽子

[编程题] 买帽子

时间限制：1秒

空间限制：32768K

度度熊想去商场买一顶帽子，商场里有N顶帽子，有些帽子的价格可能相同。度度熊想买一顶价格第三便宜的帽子，问第三便宜的帽子价格是多少？ 

输入描述:

首先输入一个正整数N（N <= 50），接下来输入N个数表示每顶帽子的价格（价格均是正整数，且小于等于1000）

输出描述:

如果存在第三便宜的帽子，请输出这个价格是多少，否则输出-1

输入例子:

10 10 10 10 10 20 20 30 30 40 40

输出例子:

30

import java.util.Scanner; public class SuanFa { public static void main(String[] args) { int[] price = new int[55];  int[] NewPrice = new int[1005]; Scanner scaner = new Scanner(System.in); int count = scaner.nextInt(); int k = 0; for(int j= 0;j< count;j++) NewPrice[j] = 0; for(int i=0;i<count;i++) { int p = scaner.nextInt(); NewPrice[p]++; if(NewPrice[p] == 1) price[k++] = p;  } int thirdP = getThirdPrice(price,0,k-1,k); if(thirdP == -1) System.out.println(-1); else   System.out.println(thirdP); } static int getThirdPrice(int[] price,int low,int high,int count) { if(count < 3)   return -1; int index = getIndex(price, low, high); while(index != 2) {  if(index == 2) break;  else if(index > 2) index = getIndex(price,low,index-1);  else index = getIndex(price,index+1,high); } return price[2]; } static int getIndex(int[] price,int low,int high) { int pivot = price[low]; while(low < high) { while(low < high && price[high] >= pivot) high--; price[low] = price[high]; while(low < high && price[low] <= pivot) low++; price[high] = price[low]; } price[low] = pivot; return low;} }