facebook一道面试题，求效率算法

Question

最近求职，facebook发来入门测试题，其中一道如下：
题意翻译过来大概是求一个矩阵内每个元素排序位置矩阵。举个例子：
矩阵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  2  2
1  3  3
3  1  1
问：由矩阵A得到矩阵C的算法？我目前想法是先将A每一列排序，得到一个只有一列的数组，然后将A中该列元素依次遍历该数组，找到同元素后，用数组中该元素的位置i替换该元素。A中所有列进行同样的操作，生成相应数组，最后将这些数组组成一个矩阵。有更有效率的算法吗？

Answer 1

我也不是很明白，A-》B还可以理解，但C是怎么一回事就不明白了。
看了你的算法，和我想的一样。

Answer 2

facebook?
就是被墙的那个吗？

Answer 3

如果只考虑时间复杂度我觉得可以用Map

Answer 4

没有他的意思是把a中的每个元素在b中的行数组成新的矩阵c。lz给的算法已经不错了，因为你只是算9个数的矩阵。还有一种思想就是将你的每一列数组写成一个类，class中有元素n=元素所在行数，a[]=每一列每一行的元素，数组长度a.length=3，这样你算a中每一列的每一行元素所在b的行数只需要调用class中的方法就可以了，不用写三个数组了，并且也符合代码书写的弱耦合性，即修改矩阵的元素不会影响算法

Answer 5

题目的意思我觉得是要求输入矩阵A然后计算出C吧，矩阵B只是计算过程中的产物所以我认为应该在生成排序的过程中就已经生成好C了实际上你应该将第一个元素变成class Item{int v, int index}
v就是A矩阵中的相应值，index是行号然后对每列排序时，实际上是对Item排序，大小比较是以v为准，这样排序后生成的矩阵B就可以轻松得到矩阵C了

Answer 6

将每一个元素变成class Item

Answer 7

试试，应该不是最有效的，望抛砖引玉，呵呵import java.util.*;public class GetPos {
    public static void main(String[] args){
        int[][] aa = {{68,36,22},{59,77,39},{81,20,17}};
        int[][] bb = new int[3][3];
        int[][] pp = new int[3][3];
        int pos = 0;        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                bb[j][i] = aa[i][j];
            }
        }        for (int[] b : bb) {
            List<Integer> temp = new ArrayList<Integer>();
            for (int i = 0; i < 3; i++) {
                temp.add(b[i]);
            }
            Collections.sort(temp);
            for (int i = 0; i < 3; i++) {
                pos = temp.indexOf(b[i]);
                b[i] = pos + 1;
            }
        }        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                pp[j][i] = bb[i][j];
            }
        }        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                System.out.print(pp[i][j] + " ");
                if (j == 2) System.out.println();
            }
        }
}}

Answer 8

程序如下：
import java.util.Scanner;
import java.util.*;public class JuZheng {
   public static void main(String[] args){
    int n=0,m=0;
    System.out.println("请输入矩阵的行数和列数:\n");
    Scanner sc=new Scanner(System.in);
    n=sc.nextInt();
    m=sc.nextInt();
    int[][] a=new int[n+1][m+1];
    int[][] ans=new int[n+1][m+1];
    int[] b=new int[n+1]; b[0]=-32767;
    System.out.println("请输入题给矩阵:\n");
    int i,j,i1,j1;
    for(i=1;i<=n;i++)
     for(j=1;j<=m;j++)
     a[i][j]=sc.nextInt();
    for(j=1;j<=m;j++){
     for(i=1;i<=n;i++)
     b[i]=a[i][j];
       Arrays.sort(b);
       for(i1=1;i1<=n;i1++){
        for(j1=1;j1<=n;j1++)
        if(a[i1][j]==b[j1])
        break;
        ans[i1][j]=j1; b[j1]=b[0];
       }
       
    }
    System.out.println("所求的位置矩阵为:");
    for(i=1;i<=n;i++){
     System.out.println();
      for(j=1;j<=m;j++)
      System.out.print(ans[i][j]+" ");
    }
    
   }
}
运行结果如下：请输入矩阵的行数和列数:3 3
请输入题给矩阵:68  36  22 
59  77  39 
81  20  17 
所求的位置矩阵为:2 2 2 
1 3 3 
3 1 1 

Answer 9

public static void main(String[] args) {
int[][] aa = { { 68, 36, 22 }, { 59, 77, 39 }, { 81, 20, 17 } };
int [][]pos = new int[3][3];
for(int i=0;i<aa.length;i++){
for(int j=0;j<3;j++){
pos[i][j] = 1;
}
}

//找排序后的位置位置
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
for(int k=0;k<3;k++){
if( k != j && aa[k][i]<aa[j][i]){
pos[j][i]++;
}
}
}

}

for(int i=0;i<3;i++){
for(int j=0;j<3;j++)
System.out.print(pos[i][j]+"");
System.out.println();
}


}

Answer 10

public class juZheng {
    public static void main(String[] args) {
        int[][] shuZuA={{68,36,22},{59,77,39},{81,20,17}};
        int[][] shuZuC=new int[3][3];
        for(int i=0;i<3;i++)
        {
         for(int j=0;j<3;j++)
             shuZuC[i][j]=1;
        }
        int num1=1,num2=1,num3=1;
       for(int i=0;i<3;i++)
        {
         for(int j=0;j<3;j++)
         {
         if(shuZuA[0][i]>shuZuA[j][i])
          shuZuC[0][i]++;
          if(shuZuA[2][i]>shuZuA[j][i])
          shuZuC[2][i]++;
          shuZuC[1][i]=6/shuZuC[0][i]/shuZuC[2][i];
         }
        }
         for(int m=0;m<3;m++)
         {
         for(int n=0;n<3;n++)
         System.out.print (shuZuC[m][n]+"  ");
         System.out.println ();
         }
    }
}

Answer 11

就是选择排序
public class Test {
public static void main(String[] args){
int[][] m={
{68,36,22},
{59,77,39},
{81,20,17}
}; int[][] idxM={
{1,1,1},
{2,2,2},
{3,3,3}
};

int rowCnt,colCnt,minVal,idx,temp;
rowCnt=colCnt=m.length;

for(int col=0;col<colCnt;col++){
//选择排序
for(int row=0;row<rowCnt;row++){
minVal=m[row][col];
idx=row;

for(int i=row+1;i<rowCnt;i++){
if(m[i][col]<minVal){
idx=i;
}
}

temp=m[row][col];
m[row][col]=m[idx][col];
m[idx][col]=temp;

temp=idxM[row][col];
idxM[row][col]=idxM[idx][col];
idxM[idx][col]=temp;
}
}

System.out.println("排序后:");
outputMatrix(m);

System.out.println("index矩阵:");
outputMatrix(idxM);
  }


public static void outputMatrix(int[][] m){
if(m==null||m.length==0) return;

for(int[] row:m){
for(int item:row){
System.out.print(item+"\t");
}
System.out.print("\n");
}
}
}

Answer 12

每列数绝无重复的话，建个从数据到位置的HashMap
有重复的话，建包含数据和位置的类并实现由数据排序的Comparable接口，任选一个O(nlogn)的排序算法对每一列排序

Answer 13

谢谢楼上所有热心的朋友！这两天有点忙，所以才过来。我仔细看了所有朋友的留言，并且对贴出的代码作了比较测试。除了21楼的朋友贴出的代码结果不对之外，其它所有的代码都得出了正确的矩阵。效率上，15,16,17楼难分伯仲。但是15L没有做特定矩阵限制，可应用性更广。因为我只是举个3x3的矩阵例子，如果是4x5的矩阵，16L，17L的代码就需要做修改。16L的代码非常简洁，佩服！18L的朋友所提出的最简单的方法，道理是很简单，但操作过程不简单。可能我没说清楚，这个long distance面试是需要把代码写出来发过去的，所有的想法全靠代码表达。18L朋友所提的方法，需要多次比较，不说操作上，我认为效率上难如人意。同时感谢14L的抛砖引玉。我按照自己的分析结贴了。最后想问15L的，“b[0]=-32767;"这句代码起的作用是什么？谢谢楼上所有的朋友。 

Answer 14

可以参考下面的两篇文章，挺好的，
第一篇讲的是如何登陆facebook和外国的网站，
第二篇是关于facebook架构，如何在上面开发属于自己的游戏，和游戏集成的文章的。http://www.docin.com/p-54714220.html
http://www.docin.com/p-46592011.html

Answer 15

function sort(A) {
    var len = A.length,
        C = new Array(len),
        i, j, k, idx;
    for (i = 0; i < len; i++) {
        C[i] = new Array(len);
        for (j = 0; j < len; j++) {
            idx = 1;
            for (k = 0; k < len; k++) {
                if (A[i][j] > A[k][j]) {
                    idx++;
                }
            }
            C[i][j] = idx;
        }
    }
    return C;
}var m = sort([[68, 36, 22], [59, 77, 39], [81, 20, 17]]);
console.log(m);