題不再難，在于優(yōu)化

這道題之前做過(guò)。

題目是：

在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。 請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)

之前自己做的時(shí)間復(fù)雜度略高。主要的思路是目標(biāo)數(shù)是target，首先與二維數(shù)組的第一行最后一列的數(shù)比較，與target比較的數(shù)如果大于等于target，根據(jù)題目中數(shù)組的特性，說(shuō)明有可能在這一行中，遍歷這一行與target比較，如果有，返回true；如果沒(méi)有在此行中，繼續(xù)與下一行最后一列的數(shù)字比較，繼續(xù)判斷。代碼如下：

1 public static boolean Find(int target, int [][] array) { 2 //從第一行開(kāi)始 3 for(int i=0;i<array.length;i++){ 4 //從最后一列開(kāi)始 5 int j = array[i].length-1; 6 //for(int j = array[i].length-1;j>=0;j--){ 7 //如果最后一列的數(shù)比目標(biāo)數(shù)大，就挨個(gè)與這一行的每個(gè)數(shù)進(jìn)行比較。 8 if(array[i][j] >= target){ 9 for(int k:array[i]){ 10 if(k==target){ 11 return true; 12 } 13 } 14 } 15 //} 16 } 17 return false; 18 }

?

最壞的情況，查找不到target時(shí)，時(shí)間復(fù)雜度為O(n^2).

書(shū)中給出了更為優(yōu)化的代碼，時(shí)間復(fù)雜度為O(n)，如下：

1 public static boolean find0(int target, int [][] array){ 2 boolean Found = false; 3 int row = 0; 4 int column = array[0].length-1; 5 6 if(array!=null && array.length >0 && array[0].length> 0){ 7 8 while(row < array.length && column >= 0){ 9 if(array[row][column] == target){ 10 Found = true; 11 break; 12 }else if(array[row][column]>target){ 13 column--; 14 }else{ 15 row++; 16 } 17 18 } 19 20 } 21 22 return Found; 23 }

主要是用了排除多余的行與列，縮小范圍的方法。

根據(jù)給出數(shù)組的特性，首先選取數(shù)組右上角的數(shù)字。如果該數(shù)字等于要查找的數(shù)字，則查找過(guò)程結(jié)束。如果該數(shù)字大于要查找的數(shù)字，則去除該數(shù)字所在列。如果該數(shù)字小于要查找的數(shù)字，則去除該數(shù)字所在行。這樣逐步縮小范圍，或者找到要查找的數(shù)字，或者查找范圍為空。

還是那句話(huà)，優(yōu)化很重要。

轉(zhuǎn)載于:https://www.cnblogs.com/weiziqiang/p/8886563.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專(zhuān)家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的面试题目4：二维数组中的查找的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。