Блог пользователя bayram

Young tableaus
Автор bayram, 11 лет назад, По-английски

An MxN Young tableau is an MxN matrix such that the entries of each row are in sorted order from left to right and the entries of each column are in sorted order from top to bottom. Some of the entries of a Young tableau may be infinity, which we treat as nonexistent elements. Thus, a Young tableau can be used to hold r <= mn finite numbers.

How to find an O(M+N) — time algorithm to determine whether a given number is stored in a given MxN Young tableau?
(source : Introduction to Algorithms)

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Hint: Can you find a way to eliminate an entire row or column of the tableau based on the value of the top-right element?

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Are nonexistent infinity elements placed to the right/bottom edge of the tableau (since rows and columns are sorted); or they could appear anywhere in the matrix?

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

If you have an opencup account (or friend who has XD) you can check your solution there. problem link (C): http://opencup.ru/files/oce/gp2/problems-e.pdf

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится 
bool search (int a[N][M], int x) {
	int i=0, j=M-1;
	while (i<N && j>=0) {
		if (a[i][j] == x)
			return true;
		if (a[i][j] < x)
			i++;
		else
			j--;
	}
	for (; i<N; i++)
		if (a[i][j] == x)
			return true;
	for (; j>=0; j--)
		if (a[i][j] == x)
			return true;
	return false;
}
→ Ответить