题目:
有一个数字矩阵(二维数组),
矩阵的每行从左到右是递增的,
矩阵从上到下是递增的,
请编写程序在这样的矩阵中查找某个数字是否存在,要求:时间复杂度小于O(N)。
=========================================================================
思路:
总体思路:
(1).
自定义函数:
实现逻辑:
因为是杨氏矩阵,所以一行中最右边的数是最大的,
这个最大值如果比要找的值都小的话,那就可以排除这一行,
列也是同理。
函数参数接收 二维数组名、要查找的数、
存放矩阵行数的变量的指针(地址)、存放矩阵列数的变量的指针(地址)。
通过两个变量找出二维数组第一行的最大值,
使用 while循环 ,如果未查找到 二维数组的最大行数 且 列数未到最小列,
(行的最右边的数是最大的列,逐渐判断直到最小列)
则继续查找。
(2).
在while循环中:
使用 if条件判断语句,判断第一行最大值是否小于要找的值,
如果小于那么这一行不可能有要查找的值,可以排除这一行将指针移到下一行,
如果最大值大于要查找的值,那么该值就在这一行,逐渐移动列数在改行进行查找,
如果要查找的值直接就和该行最大值相等 或 通过调整行数和列数找到了,
则通过 矩阵的行数列数变量的指针 设置找到的行数和列数,
跳出循环还未找到的话,则将k的“坐标”设置为(-1,-1),表未找到。
(3).
主函数:
给出一个杨氏矩阵(二维数组),
输入要在矩阵中找的数,
设置矩阵的 行 和 列 。
使用自定义函数进行查找,
函数参数为 二维数组名、要查找的数、
矩阵行数变量的指针(地址)、矩阵列数变量的指针(地址)。
通过函数的查找情况打印相应情况。
第一步:
自定义函数:
实现逻辑:
因为是杨氏矩阵,所以一行中最右边的数是最大的,
这个最大值如果比要找的值都小的话,那就可以排除这一行,
列也是同理。
函数参数接收 二维数组名、要查找的数、
存放矩阵行数的变量的指针(地址)、存放矩阵列数的变量的指针(地址)。
通过两个变量找出二维数组第一行的最大值,
使用 while循环 ,如果未查找到 二维数组的最大行数 且 列数未到最小列,
(行的最右边的数是最大的列,逐渐判断直到最小列)
则继续查找。
实现代码:
#include <stdio.h> //自定义函数: void young_table_search(int arr[3][3], int k, int* px, int* py) { //通过两个变量找出二维数组第一行的最大值: //行和列是从0开始的, int x = 0; //二维数组的行,从第一行进行查找 int y = *py - 1; //二维数组的列,从最大列开始查找, //使用 while循环 进行查找: while (x<=*px-1 && y>=0) //x<=*px-1 -- 未查找到最大行数 //y>=0 -- 未调整到最小列数 { } } int main() { return 0; }
实现图片:
第二步:
在while循环中:
使用 if条件判断语句,判断第一行最大值是否小于要找的值,
如果小于那么这一行不可能有要查找的值,可以排除这一行将指针移到下一行,
如果最大值大于要查找的值,那么该值就在这一行,逐渐移动列数在改行进行查找,
如果要查找的值直接就和该行最大值相等 或 通过调整行数和列数找到了,
则通过 矩阵的行数列数变量的指针 设置找到的行数和列数,
跳出循环还未找到的话,则将k的“坐标”设置为(-1,-1),表未找到。
实现代码:
#include <stdio.h> //自定义函数: void young_table_search(int arr[3][3], int k, int* px, int* py) { //通过两个变量找出二维数组第一行的最大值: //行和列是从0开始的, int x = 0; //二维数组的行,从第一行进行查找 int y = *py - 1; //二维数组的列,从最大列开始查找, //使用 while循环 进行查找: while (x<=*px-1 && y>=0) //x<=*px-1 -- 未查找到最大行数 //y>=0 -- 未调整到最小列数 { if (arr[x][y] < k) //第一行最大值 小于 k { x++; //排除这一行,移到下一行 } else if (arr[x][y] > k) //第一行最大值 大于 k { y--; //k就在这一行,移到列进行查找 } else //找到了:把k的行和列赋给指针px和py { *px = x; *py = y; return; } } //自定义未找到的情况: *px = -1; *py = -1; } int main() { return 0; }
实现图片:
第三步:
主函数:
给出一个杨氏矩阵(二维数组),
输入要在矩阵中找的数,
设置矩阵的 行 和 列 。
使用自定义函数进行查找,
函数参数为 二维数组名、要查找的数、
矩阵行数变量的指针(地址)、矩阵列数变量的指针(地址)。
通过函数的查找情况打印相应情况。
实现代码:
#include <stdio.h> //自定义函数: void young_table_search(int arr[3][3], int k, int* px, int* py) { //通过两个变量找出二维数组第一行的最大值: //行和列是从0开始的, int x = 0; //二维数组的行,从第一行进行查找 int y = *py - 1; //二维数组的列,从最大列开始查找, //使用 while循环 进行查找: while (x<=*px-1 && y>=0) //x<=*px-1 -- 未查找到最大行数 //y>=0 -- 未调整到最小列数 { if (arr[x][y] < k) //第一行最大值 小于 k { x++; //排除这一行,移到下一行 } else if (arr[x][y] > k) //第一行最大值 大于 k { y--; //k就在这一行,移到列进行查找 } else //找到了:把k的行和列赋给指针px和py { *px = x; *py = y; return; } } //自定义未找到的情况: *px = -1; *py = -1; } int main() { //给出一个杨氏矩阵: int arr[3][3] = { 1,2,3,4,5,6,7,8,9 }; // 1 2 3 // 4 5 6 // 7 8 9 //输入要找的数: int k = 0; scanf("%d", &k); //设置矩阵的行和列: int x = 3; //矩阵的行 int y = 3; //矩阵的列 //使用自定义函数进行查找: young_table_search(arr, k, &x ,&y); //根据情况大于相应情况: if (x==-1 && y==-1) //未找到 { printf("未找到"); } else //找到了 { printf("找到了,它的下标为:第%d行 第%d列", x, y); } return 0; }
实现图片:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
文章来源:https://www.toymoban.com/news/detail-605824.html
最终代码和实现效果
最终代码:
#include <stdio.h> //自定义函数: void young_table_search(int arr[3][3], int k, int* px, int* py) { //通过两个变量找出二维数组第一行的最大值: //行和列是从0开始的, int x = 0; //二维数组的行,从第一行进行查找 int y = *py - 1; //二维数组的列,从最大列开始查找, //使用 while循环 进行查找: while (x<=*px-1 && y>=0) //x<=*px-1 -- 未查找到最大行数 //y>=0 -- 未调整到最小列数 { if (arr[x][y] < k) //第一行最大值 小于 k { x++; //排除这一行,移到下一行 } else if (arr[x][y] > k) //第一行最大值 大于 k { y--; //k就在这一行,移到列进行查找 } else //找到了:把k的行和列赋给指针px和py { *px = x; *py = y; return; } } //自定义未找到的情况: *px = -1; *py = -1; } int main() { //给出一个杨氏矩阵: int arr[3][3] = { 1,2,3,4,5,6,7,8,9 }; // 1 2 3 // 4 5 6 // 7 8 9 //输入要找的数: int k = 0; scanf("%d", &k); //设置矩阵的行和列: int x = 3; //矩阵的行 int y = 3; //矩阵的列 //使用自定义函数进行查找: young_table_search(arr, k, &x ,&y); //根据情况大于相应情况: if (x==-1 && y==-1) //未找到 { printf("未找到"); } else //找到了 { printf("找到了,它的下标为:第%d行 第%d列", x, y); } return 0; }
实现效果
文章来源地址https://www.toymoban.com/news/detail-605824.html
到了这里,关于C语言:杨氏矩阵中查找某数(时间复杂度小于O(N))的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!