facebook一道面试题，求效率算法解决方法-Java教程-爱易网页

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

日期：2014-05-20　浏览次数：20878 次

facebook一道面试题，求效率算法
最近求职，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中所有列进行同样的操作，生成相应数组，最后将这些数组组成一个矩阵。有更有效率的算法吗？

------解决方案--------------------
程序如下：
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
------解决方案--------------------

Java code

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();
        }
        
        
    }

------解决方案--------------------
Java code
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 ();
            }
    }
}

免责声明： 本文仅代表作者个人观点，与爱易网无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。

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

相关资料更多>

推荐阅读更多>