TopCoder problem "NoisySensor" used in SRM 235 (Division II Level One)

Problem Statement

You are processing data obtained from a temperature sensor in a physics experiment. The data consists of an array of integers that represents the measured temperature as a function of time. Unfortunately, the sensor is of poor quality and has introduced some random noise into the data. You have decided to apply a median filter to the temperature data in order to reduce the effect of this noise.

In the context of this problem, median filtering is an operation on an array that replaces each element i except the first and last with the median value of itself and its two immediate neighbors (the three elements i, i-1, and i+1). The first and last elements are missing a neighbor, so median filtering does not affect them.

Write a class NoisySensor with a method medianFilter that takes a int[] data with the noisy sensor values at each time point and returns a int[] with the median-filtered version of data.

Definition

Class:	NoisySensor
Method:	medianFilter
Parameters:	int[]
Returns:	int[]
Method signature:	int[] medianFilter(int[] data)
(be sure your method is public)

Notes

The median of 3 numbers is the "middle number". To find the median, sort the 3 numbers, and then look at the second element.

Constraints

data will contain between 1 and 50 elements, inclusive.

Each element of data will be between -2147483648 and 2147483647, inclusive.

Examples

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Returns: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

Here the median filter produces no change.

{10, 1, 9, 2, 8}

Returns: {10, 9, 2, 8, 8 }

Here are the medians computed:

Median of 10, 1, 9 : 9
Median of 1, 9, 2  : 2
Median of 9, 2, 8  : 8

{500, 500, 500, 500, 500}

Returns: {500, 500, 500, 500, 500 }

{-2147483648, 2147483647}

Returns: {-2147483648, 2147483647 }

{432296535, 1983848899, -434724194, 135703525, -1146336142,
-680568092, -1183352724, 1337550909, -1597342716, -1901441857,
1726722019, -558651015, 649930787, 1889036519, 1752815826,
930647381, -852547667, 2028345278, -1835531493, -1040566300,
-1566043783, -1282411107, -1123988603, 2132078516, -1169614369,
-523503536, 1466102514, -2003903121, -779001645, 1919742042,
1210980485, -9273881, 1033032137, -1474003783, 296280591,
920184999, -1235054743, -1329769514, -1727085135}

Returns: 
{432296535, 432296535, 135703525, -434724194, -680568092, -1146336142, -680568092, -1183352724, -1597342716, -1597342716, -558651015, 649930787, 649930787, 1752815826, 1752815826, 930647381, 930647381, -852547667, -1040566300, -1566043783, -1282411107, -1282411107, -1123988603, -1123988603, -523503536, -523503536, -523503536, -779001645, -779001645, 1210980485, 1210980485, 1033032137, -9273881, 296280591, 296280591, 296280591, -1235054743, -1329769514, -1727085135 }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4019

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6534&pm=4019

Writer:

the_one_smiley

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Simple Math