成品模板网站,求制作网站,上海新政策,石柱土家族网站建设什么是杨氏矩阵#xff1f;
概念#xff1a;
有一个数字矩阵#xff0c;矩阵的每行从左到右是递增的#xff0c;矩阵从上到下是递增的
eg#xff1a;
1 2 3
4 5 6
7 8 9
题目#xff1a;
请编写程序在这样的矩阵中查找某个数字是否存在。
要求#xff1a;时间复…什么是杨氏矩阵
概念
有一个数字矩阵矩阵的每行从左到右是递增的矩阵从上到下是递增的
eg
1 2 3
4 5 6
7 8 9
题目
请编写程序在这样的矩阵中查找某个数字是否存在。
要求时间复杂度小于O(N);
分析 我们仔细分析不难发现对于杨氏矩阵来说 右上角和左下角的元素是有特点的。 右上角的元素是一行中最大的一列中最小的。 左下角的元素是一行中最小的是一列中最大的。 所以我们可以从右上角或者左下角开始查找。 比如 从右上角开始查找的时候右上角的元素比我们要查找元素小我们就可以去掉右上角元素所在的这一行 右上角的元素比我们要查找的元素大我们就可以去掉右上角元素所在的这一列。 然后依然找右上角的元素继续和要查找的元素与比较。 这样每一次比较去掉一行或者去掉一列。 这个查找效率是高于遍历数组元素的所以时间复杂度是小于O(N)也满足题目要求。 find_k(int arr[3][3], int r, int c,int k)
{int x 0;int y c - 1;while (1){if (arr[x][y] k){arr[x][y] arr[x][y];//x;}else if (arr[x][y] k){arr[x][y] arr[x][y--];//y--;}else{printf(找到了位置为%d,%d, x, y);break;}}
}
int main()
{int arr[3][3] { 1,2,3,4,5,6,7,8,9 };int k 7;find_k(arr, 3, 3,k);return 0;
}
优化传地址过去可以直接返回到主函数判断
int find_k(int arr[3][3], int *px, int *py, int k)
{int x 0;int y *py-1;int flag 0;while (x *px - 1 y0){if (arr[x][y] k){x;}else if (arr[x][y] k){y--;}else{*px x;*py y;flag 1;return 1;}}if (flag 0)return 0;}
int main()
{int arr[3][3] { 1,2,3,4,5,6,7,8,9 };int k 7;int x 3;int y 3;int ret find_k(arr,x,y,k);if (ret 0)printf(找不到了);if(ret 1)printf(下标为%d,%d, x,y);return 0;
}
