C語言楊氏矩陣中查找元素的示例代碼
題目名稱：
楊氏矩陣
題目?jī)?nèi)容：
有一個(gè)數(shù)字矩陣，矩陣的每行從左到右是遞增的，矩陣從下到上遞增的（楊氏矩陣的定義），請(qǐng)編寫程序在這樣的矩陣中查找某個(gè)數(shù)字是否存在。
形如這樣的矩陣就是楊氏矩陣（本質(zhì)上是一個(gè)二維數(shù)組）
要求：
時(shí)間復(fù)雜度小于O(N)
解題思路：
因?yàn)轭}目要求時(shí)間復(fù)雜度小于O（N），所以我們不能用暴力枚舉遍歷去解決這道題。
如何去簡(jiǎn)化時(shí)間復(fù)雜度呢？
我們首先要知道具體簡(jiǎn)化的點(diǎn)在哪里，O（N）是因?yàn)槲覀儽闅v一個(gè)一個(gè)去排除，最差的情況下，我們需要排除n次，因?yàn)楸闅v一次，排除1個(gè)。那我們就有這樣的簡(jiǎn)化思想，遍歷一次，可以排除多個(gè)元素，這樣時(shí)間復(fù)雜度肯定小于O（N）。
帶著這樣的思路去想，我們發(fā)現(xiàn)最右上角的元素很特殊。
因?yàn)樗且恍兄凶畲蟮脑?，也是一列中最小的元素?/p>
如果比它小，直接排除列。
如果比它大，直接排除行。
并且這樣的方法可以一直循環(huán)下去，直到遍歷完整個(gè)數(shù)組
這也就相當(dāng)于我們遍歷了一個(gè)元素，可以排除一行/一列的元素，大大減少了時(shí)間復(fù)雜度，滿足題目要求。
TIP：如何自定義函數(shù)返回兩個(gè)值？
我們知道函數(shù)的返回值只能返回一個(gè)值，如果題目要求我們返回兩個(gè)甚至更多的值怎么辦呢？
這個(gè)時(shí)候我們就可以利用函數(shù)的參數(shù)，我們傳參，傳我們需要返回參數(shù)的地址過去，這樣在自定義函數(shù)中我們就可以返回我們想要的參數(shù)！
源碼：
int young_search(int arr[3][3], int row, int col, int k, int* x, int* y)
{
int ret = 0;
while (ret < row && col >= 0)
{
if (arr[ret][col - 1] == k)
{
*x = ret + 1;
*y = col;
return 1;
}
else if (arr[ret][col - 1] > k)
{
col--;
}到此這篇關(guān)于C語言楊氏矩陣中尋找元素的示例代碼的文章就介紹到這了,更多相關(guān)C語言楊氏矩陣尋找元素內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C語言解3元1次方程組 用初中學(xué)的最基本的聯(lián)合消元法
最近就想自己能不能先寫個(gè)算線性方程組的程序呢？后來就想了這么個(gè)方法，暫時(shí)只能算3元的，任意元的接下來繼續(xù)想。有太多硬編碼，希望有興趣的讀者可以給點(diǎn)修改建議2013-11-11
這篇文章主要介紹了C++ 中類的拷貝、賦值、銷毀的實(shí)例詳解的相關(guān)資料,希望通過本文能幫助到大家，需要的朋友可以參考下2017-09-09
這篇文章主要介紹了詳解C語言數(shù)組靈活多變的訪問形式，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-01-01
這篇文章主要為大家介紹了C語言的字符函數(shù)和字符串函數(shù)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01
Boost是為C++語言標(biāo)準(zhǔn)庫提供擴(kuò)展的一些C++程序庫的總稱。Boost庫是一個(gè)可移植、提供源代碼的C++庫，作為標(biāo)準(zhǔn)庫的后備，是C++標(biāo)準(zhǔn)化進(jìn)程的開發(fā)引擎之一，是為C++語言標(biāo)準(zhǔn)庫提供擴(kuò)展的一些C++程序庫的總稱2022-11-11
C++ 中 const 和 static 關(guān)鍵字用法及定義
本文給大家介紹C++中const和static 關(guān)鍵字用法及定義,本文通過實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友參考下吧2025-09-09
本文主要介紹了Qt多線程安全更新QLabel的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2026-02-02
最近小編在研究Tree Widget樹形控件的相關(guān)知識(shí)，這種控件其實(shí)有時(shí)還是很有用處的，我主要利用的是帶有復(fù)選框的樹形控件，下面通過實(shí)例代碼給大家介紹下Qt中樹形控件Tree Widget的一些使用方法，感興趣的朋友一起學(xué)習(xí)吧2021-11-11
黃金礦工作為經(jīng)典的單機(jī)小游戲，一直深受大家的喜愛。本文將用Matlab制作這一款經(jīng)典的游戲，文中的實(shí)現(xiàn)步驟講解詳細(xì)，感興趣的可以了解一下2022-03-03
C語言庫函數(shù)是把自定義函數(shù)放到庫里，是別人把一些常用到的函數(shù)編完放到一個(gè)文件里，供程序員使用，下面讓我們一起來詳細(xì)了解它2022-07-07