## TopCoder SRM 208 TallPeople

## Problem Statement

Link to original problem statement

A group of people stand before you arranged in rows and columns. Looking from above, they form an R by C rectangle of people. You will be given a String[] people containing the height of each person. Elements of people correspond to rows in the rectangle. Each element contains a space-delimited list of integers representing the heights of the people in that row. Your job is to return 2 specific heights in a int[]. The first is computed by finding the shortest person in each row, and then finding the tallest person among them (the “tallest-of-the-shortest”). The second is computed by finding the tallest person in each column, and then finding the shortest person among them (the “shortest-of-the-tallest”).

**Definition**

Class: TallPeople

Method: getPeople

Parameters: String[]

Returns: int[]

Method signature: int[] getPeople(String[] people)

**Constraints**

– people will contain between 2 and 50 elements inclusive.

– Each element of people will contain between 3 and 50 characters inclusive.

– Each element of people will be a single space-delimited list of positive integers such that:

1) Each positive integer is between 1 and 1000 inclusive with no extra leading zeros.

2) Each element contains the same number of integers.

3) Each element contains at least 2 positive integers.

4) Each element does not contain leading or trailing whitespace.

**Examples**

0)

{“9 2 3”,

“4 8 7”}

Returns: { 4, 7 }

The heights 2 and 4 are the shortest from the rows, so 4 is the taller of the two. The heights 9, 8, and 7 are the tallest from the columns, so 7 is the shortest of the 3.

1)

{“1 2”,

“4 5”,

“3 6”}

Returns: { 4, 4 }

2)

{“1 1”,

“1 1”}

Returns: { 1, 1 }

## Analysis

还是个很简单的问题。。木有任何技术含量，先建立二维数组，把int从string里弄出来，然后去找每一排的最大最小值之类的。

## My code

package tc.srm.srm208; public class TallPeople { public static int[] getPeople(String[] people){ // x = row size, y = column size int x = people.length, y = 1; // Use people0 to find the column size char [] people0 = people[0].toCharArray(); for (int i = 0; i < people0.length; i++) { if (people0[i] == ' ') { y++; } } int [][] matrix = new int [x][y]; // Fill the matrix with parsed int for (int i = 0; i < x; i++) { int current = 0; int nextSpace; for (int j = 0; j < y; j++) { nextSpace = people[i].indexOf(' ', current); if (nextSpace == -1) { nextSpace = people[i].length(); } matrix[i][j] = Integer.parseInt(people[i].substring (current, nextSpace)); current = nextSpace + 1; } } // Find tall in short int shortt, tallInShort = 0; for (int i = 0; i < x; i++) { shortt = 1001; for (int j = 0; j < y; j++) { if (matrix[i][j] < shortt) { shortt = matrix[i][j]; } } if (shortt > tallInShort) { tallInShort = shortt; } } // Find short in short int tall, shortInTall = 1001; for (int j = 0; j < y; j++) { tall = 0; for (int i = 0; i < x; i++) { if (matrix[i][j] > tall) { tall = matrix[i][j]; } } if (tall < shortInTall) { shortInTall = tall; } } int [] rtn = {tallInShort, shortInTall}; return rtn; } public static void main(String[] args) { String [] people; people = new String [] {"9 2 3", "4 8 7"}; System.out.println(getPeople(people)[0] + " " + getPeople(people)[1]); people = new String [] {"1 2", "4 5", "3 6"}; System.out.println(getPeople(people)[0] + " " + getPeople(people)[1]); people = new String [] {"1 1", "1 1"}; System.out.println(getPeople(people)[0] + " " + getPeople(people)[1]); } }

## Complexity

**空间复杂度是O（mn）**，m，n代表行数和列数。因为想要按行或者按列遍历，最方便的方法就是弄个二维数组了，直接通过下标读取了。 如果想做的更好当然也可以，但是要牺牲不少时间，考虑到这里数字都不大，所以无所谓了。

**时间复杂度也是O(mn)**， 确切的说O（n + mn + mn + nm + c），因为填充数组，和先按行在按列，先按列在按行各对整个数组遍历了一次。这个应该没有特别能提升的空间了吧，起码不会比O（mn）更小我觉得，不过就我这水平肯定也弄不出来更小的。。。