MedianOfMedians

SRM 137 · 2003-03-06 · by vorthys

Class Name: MedianOfMedians

Return Type: int

Method Name: median

Arg Types: (vector<string>)

Problem Statement

Recall that the median of a group of numbers is the one in the middle when the numbers are listed in non-decreasing order. Finding the median of a large data set can be expensive, but we can approximate the true median quite cheaply by finding the medians of several small samples and then finding the median of those medians.

Consider a 3-by-3 matrix of digits, where each digit is a sample from some larger data set. Find the median of medians by first calculating the median of each row of the matrix, and then calculating the median of the three medians. For example, if the matrix were

   724
   681
   331

then the medians of the three rows would be 4, 6, and 3, respectively. The median of these three values is 4.

Create a class MedianOfMedians with a method median that takes a 3-by-3 matrix of digits as a String[] matrix and returns the median of medians. Each String in matrix represents one row and contains exactly three digits.

Constraints

matrix contains exactly three elements.
Each element of matrix contains exactly three characters, each of which is a digit ('0'-'9').

Examples

{ "724", "681", "331" }
Returns: 4

The example above.

{ "777", "777", "777" }
Returns: 7

{ "123", "456", "789" }
Returns: 5

{ "987", "321", "654" }
Returns: 5

{ "545", "565", "066" }
Returns: 5

Submissions are judged against all 29 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MedianOfMedians with a public method int median(vector<string> matrix) · 29 test cases · 2 s / 256 MB per case