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)更小我觉得,不过就我这水平肯定也弄不出来更小的。。。

发表评论

电子邮件地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据