問題
先生が小テストの点数をプログラムに入力し、最後に負の数を入力して終わりにします。この負の数は終了の合図で、点数ではありません。プログラムは、入力された順番(並べ替えはしません)で中央にある点数を報告します。点数が k 個のとき、中央は0から数えて k / 2 番目(小数点以下切り捨て)の位置です。したがって個数が偶数なら、中央の2つのうち後ろの方になります。
middle_item(values) を実装してください。
入力
values: 入力された数。最初の負の数で読み込みを終え、その数とそれ以降はすべて無視します。負の数がなければ、すべての値が点数です。
出力
中央の点数を返してください。終了の合図より前に点数が1つもなければ -1 を返します。
制約
0 ≤ values の長さ ≤ 1000
−1000 ≤ 各値 ≤ 1000
例
入力:
values = [88, 72, 95, 60, 81, -1]
期待される出力:
expected = 95
入力:
std::vector<long long> values = {88, 72, 95, 60, 81, -1};
期待される出力:
long long expected = 95;
入力:
long[] values = new long[] {88, 72, 95, 60, 81, -1};
期待される出力:
long expected = 95;
解説
点数は 88, 72, 95, 60, 81 の5個なので、中央は位置2の 95 です。
入力:
values = [10, 20, 30, 40, -5, 50]
期待される出力:
expected = 30
入力:
std::vector<long long> values = {10, 20, 30, 40, -5, 50};
期待される出力:
long long expected = 30;
入力:
long[] values = new long[] {10, 20, 30, 40, -5, 50};
期待される出力:
long expected = 30;
解説
−5 で読み込みが止まり、点数は4個残ります。位置2にあるのは 30 です。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
最初の負の数に出会うまで、値を新しいリストにコピーしましょう。
ヒント 2
要素が k 個なら、中央の添字は整数除算で k / 2 です。
ヒント 3
何もコピーされなかった場合、中央の要素はありません。
目安の計算量
時間 O(n)、追加メモリ O(n)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。