このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題文について、おおまかに説明する。
スティーブは新しい車を買いたいと思っている。ただ、お金がないので、リーズナブルな安いものを好んでいる。ただ一番安い車の品質は疑問である。そこで、スティーブは車の価格一覧から3番目に安い価格の車を買うことにした。prices[]という、整数型の車の価格が入った配列が与えられる。pricesには何度も同じ価格が現れることもあるが、それは1度数えるだけとする。prices[]で3番目に安い車の価格を返す関数を作成せよ。もし、車の価格が3種類に満たない場合は、-1を返すようにせよ。
私の解答はこちら。
import java.util.Iterator; import java.util.TreeSet; public class BuyingCheap { public int thirdBestPrice(int[] prices) { TreeSet<Integer> ts = new TreeSet<Integer>(); for( int i=0 ; i<prices.length ; i++ ){ ts.add(prices[i]); // ユニークな集合の作成 } if( ts.size() < 3 ) return -1; // 集合のサイズが2以下なら3番目に安い車はない Iterator<Integer> it = ts.iterator(); int i = 0; while( it.hasNext() ){ // イテレータを利用して3番目に小さい要素を返す if( i==2 ){ return it.next(); } it.next(); i++; } return -1; } }
得点は136.52/250。Setの使い方の良い復習になりました。TreeSetにしておくと、集合を昇順にソートしてくれるので、そのまま問題に適用可能です。
0 件のコメント:
コメントを投稿