再来讨论一下Fackbook的那道面试题

Question

我想看过那个帖子的人应该都还记得吧？原命题是：
/*
矩阵A
68  36  22
59  77  39
81  20  17
将矩阵A每列排序之后（升序排列）应该得到的矩阵是：
矩阵B:
59  20  17
68  36  22
81  77  39
这样矩阵A中每个元素在矩阵B中对应的位置就是
矩阵C：
2  3  3
1  1  1
3  2  2
问：由矩阵A得到矩阵C的算法？ 
*/
在自己的blog里（详见"关于返回二维数组排序后序号数组的问题求解"），将这个问题扩展到了不规则数组中，也就是说算法应该能解决如下问题：
/*
矩阵A
68  36  22
59  77 
81
将矩阵A每列排序之后（升序排列）应该得到的矩阵是：
矩阵B:
59  36  22
68  77  
81  
这样矩阵A中每个元素在矩阵B中对应的位置就是
矩阵C：
2  1  1
1  2  2
3  
问：由矩阵A得到矩阵C的算法？
*/
不知道各位能不能提供更好地解法。大冬天的，大家热烈讨论吧！关于blog的一些错误，也欢迎指正！

Answer 1

想了一个很笨的方法，首先把A每一列排序得到B 然后让B列中元素和A中相应列相比较找出它所在A相应列的行坐标并替换这个元素。循环就要从列开始了。
抛砖引玉，  我是菜鸟，大侠莫怪~~~

Answer 2

private static void method1() {
int[][] aa = { { 68, 36, 22 }, { 59, 77, 39 }, { 81, 20, 17 } };
int[][] po = { { 1, 1, 1 }, { 2, 2, 2 }, { 3, 3, 3 } };; int temp;
for (int i = 0; i < aa.length; i++) {
for (int j = aa.length - 1; j > 0; j--) {
for (int k = 0; k < j; k++) {
if (aa[k][i] > aa[k + 1][i]) {
temp = aa[k][i];
aa[k][i] = aa[k + 1][i];
aa[k + 1][i] = temp;

temp = po[k][i];
po[k][i] = po[k + 1][i];
po[k + 1][i] = temp;
}
}
} }
}

Answer 3

这个我也想过 不知道还能不能优化 但是目前看是O(n^3)的时间复杂度 可以拿我blog里的那个数组测试一下看看另外这个代码不算完整吧 因为po是写死的 应该再写一个根据aa数组动态生成po数组的方法

Answer 4

这些还要说吗？主要思想都出来了，剩下自己搞定
private static void method1() {
int[][] aa = { { 68, 36, 22 }, { 59, 77, 39 }, { 81, 20, 17 } };
int[][] po = new int[aa.length][aa[0].length]; // 给index数组赋初始值
for (int i = 0; i < aa.length; i++) {
for (int j = 0; j < aa[i].length; j++) {
po[i][j] = i + 1;
}
} int temp;
for (int i = 0; i < aa.length; i++) {
for (int j = aa.length - 1; j > 0; j--) {
for (int k = 0; k < j; k++) {
if (aa[k][i] > aa[k + 1][i]) {
temp = aa[k][i];
aa[k][i] = aa[k + 1][i];
aa[k + 1][i] = temp; temp = po[k][i];
po[k][i] = po[k + 1][i];
po[k + 1][i] = temp;
}
}
}
}
}