TopCoder SRM235 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。それでは、問題について説明する。

物理実験で温度が整数値で得られるセンサーを利用している。ただ、このセンサーは精度が悪く、ノイズが乗るのでメジアンフィルタを利用してノイズを減らそうと考えた。ここでいうメジアンフィルタというのは、ある注目しているi番目の測定値とその前後の測定値の中央値を返すというものである。また、最初と最後の要素は、前後のどちらかの要素がかけているので、その場合は、注目している値をそのまま返せばよいとする。data[]という配列が与えられたときに、メジアンフィルタを適用した結果得られる配列を返せ。

私の解答はこちら。

import java.util.*;
public class NoisySensor {
 public int[] medianFilter(int[] data) {
  ArrayList result = new ArrayList();
  ArrayList list = new ArrayList();
  if( data.length < 3) return data;
  result.add(data[0]);
  list.add(data[0]);
  list.add(data[1]);
  for( int i=2 ; i<data.length ; i++ ){
   list.add(data[i]);
   Collections.sort(list);
   result.add(list.get(1));
   int idx = list.indexOf(data[i-2]);
   list.remove(idx);
  }
  result.add(data[data.length-1]);
  Integer[] Warray = (Integer[])result.toArray(new Integer[0]);
  int[] array = new int[data.length];
  for( int i=0 ; i<array.length ; i++ ){
   array[i] = Warray[i].intValue();
  }
  return array;
 }
}

得点は158点、中央値はもっと上の値である。はじめてコレクションを利用したので、本を見ながら試行錯誤して解いていた。