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語言中正切的相關(guān)函數(shù)總結(jié),包括正切和反正切以及雙曲線正切等的函數(shù),需要的朋友可以參考下2015-08-08
Qt?自定義屬性Q_PROPERTY不顯示float類型的解決
這篇文章主要介紹了Qt?自定義屬性Q_PROPERTY不顯示float類型的問題及解決，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-11-11
這篇文章主要介紹了C語言實(shí)現(xiàn)的雙鏈表功能,結(jié)合完整實(shí)例形式分析了基于C語言實(shí)現(xiàn)的雙鏈表定義、添加、刪除、排序等相關(guān)操作實(shí)現(xiàn)技巧,需要的朋友可以參考下2018-04-04
C語言中strcpy和strcat的使用和模擬實(shí)現(xiàn)
strcpy()?函數(shù)是?C語言中一個(gè)非常重要的字符串處理函數(shù),其功能是將一個(gè)字符串復(fù)制到另一個(gè)字符串中,strcat函數(shù)可以將一個(gè)字符串拼接到另一個(gè)字符串的末尾,本文給大家介紹了C語言中strcpy和strcat的使用和模擬實(shí)現(xiàn),需要的朋友可以參考下2024-03-03
用C語言遞歸實(shí)現(xiàn)火車調(diào)度算法詳解
本文主要介紹了用C語言遞歸實(shí)現(xiàn)火車調(diào)度算法詳解，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-11-11
關(guān)于C++內(nèi)存中字節(jié)對(duì)齊問題的詳細(xì)介紹
本篇文章是對(duì)C++內(nèi)存中字節(jié)對(duì)齊的問題進(jìn)行了詳細(xì)的分析與總結(jié)。需要的朋友參考下2013-05-05
C++中String類的常用接口函數(shù)總結(jié)
這篇文章主要介紹了C++中Stirng類的常用接口函數(shù)，文中有詳細(xì)的代碼示例供大家參考，對(duì)我們學(xué)習(xí)C++有一定的幫助，感興趣的同學(xué)可以跟著小編一起來學(xué)習(xí)2023-06-06
C語言數(shù)據(jù)結(jié)構(gòu)之堆排序的優(yōu)化算法
堆排序Heap?Sort就是利用堆進(jìn)行排序的方法,下面這篇文章主要給大家介紹了關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)之堆排序的優(yōu)化算法的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-04-04
C語言實(shí)現(xiàn)簡(jiǎn)單的圖書管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)簡(jiǎn)單的圖書管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-03-03
這篇文章主要介紹了C語言如何實(shí)現(xiàn)BOOL類型問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-02-02