Skip to content

Latest commit

 

History

History
193 lines (132 loc) · 4.11 KB

6 矩阵.md

File metadata and controls

193 lines (132 loc) · 4.11 KB
Raw

矩阵

矩阵在计算机中表示就是二维数组。这部分内容都是有关二维数组和矩阵相关的题目。

顺时针打印矩阵

题目：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。 例如：如果输入如下矩阵：

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

则依次打印出数字1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10 。

分析：包括Autodesk、EMC在内的多家公司在面试或者笔试里采用过这道题。 难点： 各种边界条件判断，很容易搞错

一圈一圈打印，第一圈origin是(0,0),第二圈是(1,1)

void print_matrix(int **matrix,int rows,int cols);
//或
void print_matrix(int *matrix,int rows,int cols);

示例代码：

void print_matrix(int *matrix,int rows,int cols){
	if(matrix==NULL) return ;
	if(rows<=0 || cols<=0) return;

	int start = 0;
	while(start*2<cols && start*2<rows){
		print_matrix_incircle(matrix,rows,cols,start);
		start++;
	}
}

// a[i*rows+j]
void print_matrix_incircle(int *matrix,int rows,int cols,int start){
	int endX = cols-start-1;
	int endY = rows-start-1;

	//然后依次打印 上，右，下，左
	for(int i=start;i<=endX,i++){
		printf("\d ",matrix[start*rows+i]);
	}

	for(int i=start+1;i<=endY,i++){
		printf("\d ",matrix[i*rows+endX]);
	}

	for(int i=endX-1;i>=start;i--){
		printf("\d ",matrix[start*rows+i]);
	}

	for(int i=endY-1;i>start;i--){
		printf("\d ",matrix[i*rows+start]);
	}
}

测试代码见 print_matrix.c

从小到大输出矩阵的值

思路1：采用归并进行排序然后进行顺序打印 思路2：用n个指针指向每一行的第一个数，比较n个指针的数，打印最小的，然后指针后移，若无下一位，则赋值为null，直至所有数都对印完毕

void printArry(int *a,int rows,int columns)
{
    if(a==null)
        return;

    int *arr=new int[rows*(columns+1)];//添加看门狗值，INT_MAX
    for(int i=0;i<rows;i++)
        for(int j=0;j<columns+1;j++)
        {
            if(j==columns)
                arr[i*(columns+1)+j]=INT_MAX;
            else
                arr[i*(columns+1)+j]=a[i*columns+j];
        }

    int* pArr1=new int[rows];//共存有这么多行指针
    for(int i=0;i<rows;i++)
        pArr1[i]=i*(columns+1);

    while(1)
    {
        int min=arr[pArr1[0]];
        int mini=0;
        for(int i=0;i<rows;i++)
        {//第i个数组最小
            int index=pArr1[i];
            if(min>arr[index])
            {
                min=arr[index];
                mini=i;
            }
        }
        if(min==INT_MAX)
            break;//表示都达到了看门处，则跳出循环。
        cout<<min<<" ";
        pArr1[mini]++;//指针前移动
    }
}

算法复杂度时O(mn)；m是行数，n是列数；对原矩阵，增加一列，用于看门；利用类似归并排序中的整合过程，此处是整合m个有序数列，最后得到有序输出。

二维数组中的查找

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

1 3 5 7
2 5 7 12
4 6 9 23
6 9 23 75

int exist_inmatrix(int *matrix,int rows,int cols,int target);

矩阵中最大的二维矩阵

求一个矩阵中最大的二维矩阵(元素和最大).如:

1 2 0 3 4
2 3 4 5 1
1 1 5 3 0

中最大的是:

4 5
5 3

要求: (1)写出算法; (2)分析时间复杂度; (3)用C写出关键代码

int max_sum_submatrix(int *matrix,int rows,int cols,int *tmatrix,int *trows,int tcols)

矩阵中的最大上升路径

nums = [
    [9,9,4],
    [6,6,8],
    [2,1,1],
]

返回4， 最长上升路径 [1,2,6,9] ;

Google 面试题， 此题采用bfs和拓扑排序均可达到面试官的要求。笔者认为，一般的bfs可以达到hire；记忆化搜索和拓扑排序可以达到strong hire