网页建站系统,wordpress群空间,微信群如何推广网站建设,资源链接搜索引擎杨氏矩阵
有一个数字矩阵#xff0c;矩阵的每行从左到右是递增的#xff0c;矩阵从上到下是递增的#xff0c;请编写程序在这样的矩阵中查找某个数字是否存在。
要求#xff1a;时间复杂度小于O(N); 分析
若要满足要求时间复杂度小于O(N)#xff0c;就不能每一行一个个… 杨氏矩阵
有一个数字矩阵矩阵的每行从左到右是递增的矩阵从上到下是递增的请编写程序在这样的矩阵中查找某个数字是否存在。
要求时间复杂度小于O(N); 分析
若要满足要求时间复杂度小于O(N)就不能每一行一个个找。 根据杨氏矩阵的特点行递增、列递增我们可以从矩阵的右上角开始
就比如我们要找上图中的数字7
97,因为列递增 ,9是该列最小的数字都大于7所以第4列的数字都比7大排除第4列
右上角数字变为了667因为行递增6是该行最大的数字都小于7所以第1行的数字都比7小排除第1行 右上角数字变为了777找到了 代码实现
// 假设有4列x行y列key是要找的数字
int FindNum(int arr[][4], int x, int y, int key)
{int i 0;int j y - 1;//满足此循环i和j都是合法的while (j 0 i x){if (arr[i][j] key){j--;}else if (arr[i][j] key){i;}else{return 1;//找到了}}return 0;//没找到
}
杨辉三角
在屏幕上打印杨辉三角
分析
杨辉三角的特点除了外围的数字为1其他满足 数字 这列的上一行数字 上一行前一列数字
我们定义有i行j列 其中数字是1的下标满足j0或ij
其他数字的下标满足[i][j] [i-1][j] [i-1][j-1] 代码实现
#includestdio.h
//在屏幕上打印杨辉三角。
void YanghuiTriangle(int arr[][4], int n)
{for (int i 0; i n; i){for (int j 0; j i; j){if (j 0 || i j){arr[i][j] 1;}else{arr[i][j] arr[i - 1][j] arr[i - 1][j - 1];}}}//打印for (int i 0; i n; i){for (int j 0; j i; j){printf(%d , arr[i][j]);}printf(\n);}
}
int main()
{int arr[4][4] { 0 };YanghuiTriangle(arr, 4);return 0;
}
