C语言——oj刷题——杨氏矩阵

简介: C语言——oj刷题——杨氏矩阵

当我们谈到杨氏矩形时,我们指的是一种在二维数组中查找目标元素的高效算法。它是由杨氏(Yan Shi)教授提出的,因此得名为杨氏矩形。


杨氏矩形问题的场景是这样的:给定一个有序的二维数组,每一行从左到右递增,每一列从上到下递增。我们需要在这个二维数组中快速查找某个目标元素是否存在。


为了更好地理解和解决这个问题,我们将分为以下几个步骤进行讲解和编码示例:


  1. 理解杨氏矩形的特点
  2. 实现杨氏矩形查找算法
  3. 编写示例代码


1. 理解杨氏矩形的特点

杨氏矩形的特点是每一行从左到右递增,每一列从上到下递增。这意味着我们可以通过比较目标元素和当前元素的值来缩小查找范围。


具体来说,我们可以从矩形的右上角开始查找。如果目标元素比当前元素大,则目标元素必然不在当前元素的同一行,因此可以排除当前元素所在的行;如果目标元素比当前元素小,则目标元素必然不在当前元素的同一列,因此可以排除当前元素所在的列。通过这种方式,我们可以逐步缩小查找范围,直到找到目标元素或查找范围为空。


2. 实现杨氏矩形查找算法

基于上述特点,我们可以设计一个高效的杨氏矩形查找算法,具体步骤如下:

  • 初始化当前元素为矩形的右上角元素
  • 循环执行以下步骤:
  • 如果当前元素等于目标元素,则返回找到目标元素的位置
  • 如果目标元素比当前元素大,则将当前元素下移一行
  • 如果目标元素比当前元素小,则将当前元素左移一列
  • 如果循环结束仍未找到目标元素,则返回未找到的结果

3. 编写示例代码

下面是一个使用C语言编写的示例代码,演示如何实现杨氏矩形查找算法:

#include <stdio.h>
#include <stdbool.h>
 
bool yangsMatrixSearch(int matrix[3][3], int target) {
    int rows = 3; // 矩阵的行数
    int cols = 3; // 矩阵的列数
 
    // 初始化当前元素为矩阵的右上角元素
    int row = 0;
    int col = cols - 1;
 
    // 循环查找
    while (row < rows && col >= 0) {
        if (matrix[row][col] == target) {
            return true; // 找到目标元素
        } else if (matrix[row][col] < target) {
            row++; // 目标元素比当前元素大,下移一行
        } else {
            col--; // 目标元素比当前元素小,左移一列
        }
    }
 
    return false; // 未找到目标元素
}
 
int main() {
    int matrix[3][3] = {
        {1, 4, 7},
        {2, 5, 8},
        {3, 6, 9}
    };
    int target = 5;
 
    bool found = yangsMatrixSearch(matrix, target);
 
    if (found) {
        printf("目标元素 %d 存在于矩阵中\n", target);
    } else {
        printf("目标元素 %d 不存在于矩阵中\n", target);
    }
 
    return 0;
}

在上述示例代码中,我们定义了一个yangsMatrixSearch函数,该函数接受一个二维数组(矩阵)和目标元素作为参数。函数内部实现了杨氏矩形查找算法。


在main函数中,我们定义了一个3x3的矩阵和一个目标元素。然后,调用yangsMatrixSearch函数来查找目标元素是否存在于矩阵中,并根据查找结果打印相应的信息。


希望这篇博客能够帮助你理解杨氏矩形问题,并提供了详细的讲解和代码示例。如果有任何疑问,请随时向我提问。

相关文章
|
存储 C语言
【C语言】基础刷题训练4(含全面分析和代码改进示例)
【C语言】基础刷题训练4(含全面分析和代码改进示例)
139 1
|
11月前
|
机器学习/深度学习 编译器 C语言
C语言刷题(中)(保姆式详解)
C语言刷题(中)(保姆式详解)
71 0
|
C语言
【C语言刷题训练】——第7节(含代码与分析思路)
【C语言刷题训练】——第7节(含代码与分析思路)
118 0
|
测试技术 C语言 C++
【C语言刷题训练——6】鹏哥C语言刷题训练营笔记,含代码讲解改进
【C语言刷题训练——6】鹏哥C语言刷题训练营笔记,含代码讲解改进
170 0
|
存储 C语言
【C语言】鹏哥C语言刷题训练营——第5节内容笔记(含代码全面分析和改进,讲解)
【C语言】鹏哥C语言刷题训练营——第5节内容笔记(含代码全面分析和改进,讲解)
273 0
C语言刷题(循环结构程序设计)
C语言刷题(循环结构程序设计)
|
7天前
|
存储 C语言
`scanf`是C语言中用于按格式读取标准输入的函数
`scanf`是C语言中用于按格式读取标准输入的函数,通过格式字符串解析输入并存入指定变量。需注意输入格式严格匹配,并建议检查返回值以确保读取成功,提升程序健壮性。
301 0
|
2月前
|
安全 C语言
C语言中的字符、字符串及内存操作函数详细讲解
通过这些函数的正确使用,可以有效管理字符串和内存操作,它们是C语言编程中不可或缺的工具。
241 15
|
8月前
|
存储 算法 C语言
【C语言程序设计——函数】素数判定(头歌实践教学平台习题)【合集】
本内容介绍了编写一个判断素数的子函数的任务,涵盖循环控制与跳转语句、算术运算符(%)、以及素数的概念。任务要求在主函数中输入整数并输出是否为素数的信息。相关知识包括 `for` 和 `while` 循环、`break` 和 `continue` 语句、取余运算符 `%` 的使用及素数定义、分布规律和应用场景。编程要求根据提示补充代码,测试说明提供了输入输出示例,最后给出通关代码和测试结果。 任务核心:编写判断素数的子函数并在主函数中调用,涉及循环结构和条件判断。
378 23