Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 面试 » ,

杨氏矩阵的操作与计数

杨氏矩阵(Young tableau)是一种简单却很神奇的数据结构,具有类似于堆的操作和性质。在实际中可能不是很常用,但在面试中却经常遇到,比较考察程序员的算法思维能力。
本文主要讲解下杨氏矩阵的定义及一般的操作和计数问题。

一 定义和计数

杨氏矩阵是一个m x n的矩阵,它的每一行从左到右是严格单调递增的,每一列从左到右也是严格单调递增的。对于矩阵中没有元素的格子,可以填入表示无穷大的数字。对于非严格单调递增或单调递减的可以类似定义。

现在我们不考虑没有元素的格子,杨氏矩阵会变成一种不规则的形状,如

1 2 3 4
5 6 7
8 9 10
11

注意矩阵里面没有元素的格子右边和下面也必须是没有元素。

定义一个元素的钩长等于这个这个格子下边的格子数量加右边的格子数量再加上本身的这个1个格子数,如5的钩长等于 2+2+1=5。

现在可以计算把1到n这n个元素放到这个形状的钩子里面的方法总数(称为钩长公式),方法总数等于n!除以所有格子的钩长的乘积。例如,上述的结果为 11!/(1 * 2*3*4 * 3*4*5 * 4*5*6*7) = 33。

特殊地,1到2*n这2*n个数填入一个2 x n的杨氏矩阵的填法个数为 (2*n)! / (n! * (n+1)!),答案很大要求模时可以利用扩展欧几里得算法求出每个除数的逆,把除法转化为乘法。

二 初始化和打印

给定一组元素,很容易构造出一个杨氏矩阵,只要把数组从小到大排序,然后从上到下、从左到右依次在矩阵中填入数组元素,剩下的格子再填入无穷大即可。

以下的代码中把矩阵定义为全局变量,方便在函数中使用。另外用常量oo表示无穷大,初始化为一个很大的整数。

打印时就相当于打印一个矩阵,为了美观,把无穷大输出为oo的符号。

const int mx = 100, oo = 1<<30;
int Young[mx][mx], m, n;//杨氏矩阵,长,宽
void init()
{
	m = n = 4;
	int a[] = { 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16};
	int len = sizeof(a) / sizeof(a[0]);		sort(a, a+len);	
	for (int i = 0, id = 0; i < m; i++)
		for (int j = 0; j < n; j++)
			Young[i][j] = id < len ? a[id++] : oo;
}
void print()
{
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)	
			if (Young[i][j] == oo)	printf("%s ", "oo");
			else printf("%2d ", Young[i][j]);
		printf("\n");
	}
	printf("\n");
}

三 插入元素

在杨氏矩阵中插入元素类似于在堆中插入元素。首先把元素插在矩阵右下角,因为插入之后可能不满足递增的要求,于是要进行调整。根据杨氏矩阵的定义,当前位置的元素必须大于其上面和左边的元素值,如果满足这个要求则插入成功,如果不满足则把左边和上边中较大的值和当前位置的值交换,然后再迭代考虑新的当前位置是否满足要求。

如上面矩阵中插入10的具体过程为:

2 3 4 5   2 3 4 5   2 3 4 5   2 3 4 5   2 3 4 5
6 7 8 9   6 7 8 9   6 7 8 9   3 7 8 9   3 7 8 9
11 12 13 14   11 12 13 14   11 12 13 14   11 12 13 14   10 12 13 14
15 16 oo 10   15 16 10 oo   15 10 16 oo   10 15 16 oo   11 15 16 oo

在代码中实现为

int insert(int x)
{
	if (Young[m-1][n-1] != oo)	return -1; //元素已满,插入失败
	int r = m - 1, c = n - 1;	Young[r][c] = x;
	while (true)
	{
		if ((r==0 || x>Young[r-1][c]) && (c==0 || x>Young[r][c-1])) break;
		else
		{
			int newr = r, newc = c;
			if (r == 0) newc--;
			else if(c == 0) newr--;
			else if (Young[r-1][c] > Young[r][c-1]) newr--;
			else newc--;
			swap(Young[r][c], Young[newr][newc]);
			r = newr, c = newc;
		}
	}
	return 0;
}

四 查找元素

在矩阵中查找元素有两种方法,首先是查找指定的元素x是否在矩阵中。除去穷举遍历、二分查找的方法,这里有更快捷的方法,复杂度为O(m+n)。

首先考虑右上角的元素,如果为x则返回成功。如果x比它大,则x肯定在它的下面,把位置下移一行。如果x比它小,则x肯定在它的左边,把位置左移一列。移动后再对当前位置进行同样的过程直到找到或者元素不存在。

具体的实现如下所示,可以通过引用返回具体查找到的位置。

bool find(int x, int &row, int &col)
{
	int r = 0, c = n - 1;
	while (r < m && c >= 0)
		if (x > Young[r][c]) r++;
		else if(x < Young[r][c]) c--;
		else{ row = r, col = c; return true;	}
	row = -1, col = -1;	return false;
}

另外一种查找是指定要查找第k小的元素是什么。

这里需要用到一个辅助过程,求出在矩阵中有多少个元素比x小。具体求解思路跟上述查找思路类似。

int getNum(int x)
{
	int r = 0, c = n - 1, order = 0;
	while (r < m && c >= 0)
		if (x > Young[r][c]) order += c + 1, r++;
		else c--;
	return order;
}

然后可以进行查找。首先用二分搜索找到一个数x,使得矩阵中刚好有k个数比x小,然后在矩阵中比x小的数的最大值即为第k小的数。

int findMinK(int k, int &row, int &col)
{
	if (k > m * n) {row = -1, col = -1; return -1;} //非法参数
	int st = Young[0][0], ed = Young[m-1][n-1]+1, mid;
	while (true)
	{
		mid = (st & ed)  + ((st ^ ed) >> 1); //求平均数,避免溢出
		int num = getNum(mid);
		if (num == k) break;
		else if(num > k) ed = mid - 1;
		else st = mid + 1;
	}
	int r = 0, c = n - 1, mink = -oo;
	while (r < m && c >= 0)
		if (Young[r][c] >= mid)		c--;
		else
		{
			if (Young[r][c] > mink) mink = Young[r][c], row = r, col = c;
			r++;
		}
	return mink;
}

五 删除元素

具体删除一个元素x时,首先可以通过查找找到x的位置,然后把这个位置上的数置为无穷大,然后再用相同的策略对这个位置进行调整,使之最终满足杨氏矩阵的要求。

void remove(int x)
{
	int r, c;
	if (!find(x, r, c)) return; //不存在
	Young[r][c] = oo; x=oo;
	while (true)
	{
		if ((r==m-1 || x<Young[r+1][c]) && (c==n-1 || x<Young[r][c+1]))	break;
		else
		{
			int newr = r, newc = c;
			if (r == m-1) newc++;
			else if(c == n-1) newr++;
			else if(Young[r+1][c] < Young[r][c+1]) newr++;
			else newc++;
			swap(Young[r][c], Young[newr][newc]);
			r = newr, c = newc;
		}
	}
}

六 测试程序

这里写了一个简单的测试测试程序。

int main ()
{
	init(); print(); 
	insert(13); print();	insert(1); print(); 
	int x, y, t, k; bool exist;
	t = 9, exist = find(t, x, y);
	printf("%2d Exist? %d: %d %d\n", t, exist, x, y);
	t = 17, exist = find(t, x, y);
	printf("%2d Exist? %d: %d %d\n", t, exist, x, y);
	t = 9, k = findMinK(t, x, y);
	printf("%2d min num: %d(%d, %d)\n", t, k, x, y);
	t = 17, k = findMinK(t, x, y);
	printf("%2d min num: %d(%d, %d)\n", t, k, x, y);
	remove(13); print();	remove(1);print();
}
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论