搜索按行和按列排序的矩陣 · GeeksForGeeks 中文系列教程

# 搜索按行和按列排序的矩陣 > 原文： [https://www.geeksforgeeks.org/search-in-row-wise-and-column-wise-sorted-matrix/](https://www.geeksforgeeks.org/search-in-row-wise-and-column-wise-sorted-matrix/) 給定一個 n x n 矩陣和一個數字 x，找到 x 在矩陣中的位置（如果存在）。否則，打印“未找到”。在給定的矩陣中，每一行和每一列都按升序排序。設計的算法應具有線性時間復雜度。 **示例**： ``` Input: mat[4][4] = { {10, 20, 30, 40}, {15, 25, 35, 45}, {27, 29, 37, 48}, {32, 33, 39, 50}}; x = 29 Output: Found at (2, 1) Explanation: Element at (2,1) is 29 Input : mat[4][4] = { {10, 20, 30, 40}, {15, 25, 35, 45}, {27, 29, 37, 48}, {32, 33, 39, 50}}; x = 100 Output : Element not found Explanation: Element 100 is not found ``` **簡單解決方案** * **方法**：簡單的想法是遍歷數組并逐一搜索元素。 * **算法**： 1. 運行嵌套循環，外循環用于行，內循環用于列 2. 用 x 檢查每個元素，如果找到該元素，則打印“找到元素” 3. 如果找不到該元素，則打印“找不到元素”。 * **Implementation:** **``` // C++ program to search an element in row-wise // and column-wise sorted matrix #include <bits/stdc++.h> using namespace std; /* Searches the element x in mat[][]. If the? element is found, then prints its position? and returns true, otherwise prints "not found" and returns false */ int search(int mat[4][4], int n, int x) { ????if (n == 0) ????????return -1; ????//traverse through the matrix ????for(int i = 0; i < n; i++) ????{ ????????for(int j = 0; j < n; j++) ????????//if the element is found ????????if(mat[i][j] == x) ????????{ ????????????cout<<"Element found at ("<<i<<", "<<j<<")\n"; ????????????return 1; ????????} ????} ????cout << "n Element not found"; ????return 0;? } // Driver code int main() { ????int mat[4][4] = { { 10, 20, 30, 40 }, ??????????????????????{ 15, 25, 35, 45 }, ??????????????????????{ 27, 29, 37, 48 }, ??????????????????????{ 32, 33, 39, 50 } }; ????search(mat, 4, 29); ????return 0; } ``` **輸出**： ``` Element found at (2, 1) ```** * **復雜度分析**： * **時間復雜度**： `O(n^2)`。數組的單個遍歷需要 `O(n^2)`時間。 * **空間復雜度**：`O(1)`。不需要多余的空間。 **更好的解決方案**是[使用分而治之找到時間復雜度為 O（n <sup>1.58</sup> ）的元素](https://www.geeksforgeeks.org/divide-conquer-set-6-search-row-wise-column-wise-sorted-2d-array/)。有關詳細信息，請在處參考[。](https://www.geeksforgeeks.org/divide-conquer-set-6-search-row-wise-column-wise-sorted-2d-array/) **有效解決方案** * **Approach:** The simple idea is to remove a row or column in each comparison until an element is found. Start searching from the top-right corner of the matrix. There are three possible cases. 1. **給定的數字大于當前的數字**：這將確保當前行中的所有元素都小于給定的數字，因為指針已經在最右邊的元素上并且對該行進行了排序。因此，整個行將被消除，并在下一行繼續搜索。在這里消除意味著不需要搜索行。 2. **給定的數字小于當前數字**：這將確保當前列中的所有元素都大于給定的數字。因此，整個列將被消除，并繼續在前一列（即最左側的列）中進行搜索。 3. **給定的號碼等于當前的號碼**：這將結束搜索。搜索也可以從矩陣的左下角開始。 * **算法**： 1. 假設給定元素為 x，則創建兩個變量 *i = 0，j = n-1* 作為行和列的索引 2. 循環運行直到 i = 0 3. 檢查當前元素是否大于 x，然后減少 j 的計數。排除當前列。 4. 檢查當前元素是否小于 x，然后增加 i 的計數。排除當前行。 5. 如果元素相等，則打印位置并結束。 * *感謝 devendraiiit 建議采用以下方法。* * **Implementation:** ## C++ ``` // C++ program to search an element in row-wise // and column-wise sorted matrix #include <bits/stdc++.h> using namespace std; /* Searches the element x in mat[][]. If the? element is found, then prints its position? and returns true, otherwise prints "not found" and returns false */ int search(int mat[4][4], int n, int x) { ????if (n == 0) ????????return -1; ????int smallest = a[0][0], largest = a[n - 1][n - 1]; ????if (x < smallest || x > largest) ????????return -1; ????// set indexes for top right element ????int i = 0, j = n - 1;? ????while (i < n && j >= 0) { ????????if (mat[i][j] == x) { ????????????cout << "n Found at " ?????????????????<< i << ", " << j; ????????????return 1; ????????} ????????if (mat[i][j] > x) ????????????j--; ????????else // if mat[i][j] < x ????????????i++; ????} ????cout << "n Element not found"; ????return 0; // if ( i==n || j== -1 ) } // Driver code int main() { ????int mat[4][4] = { { 10, 20, 30, 40 }, ??????????????????????{ 15, 25, 35, 45 }, ??????????????????????{ 27, 29, 37, 48 }, ??????????????????????{ 32, 33, 39, 50 } }; ????search(mat, 4, 29); ????return 0; } // This code is contributed // by Akanksha Rai(Abby_akku) ``` ## C ``` // C program to search an element in row-wise // and column-wise sorted matrix #include <stdio.h> /* Searches the element x in mat[][]. If the? element is found, then prints its position? and returns true, otherwise prints "not found" and returns false */ int search(int mat[4][4], int n, int x) { ????if (n == 0) ????????return -1; ????int smallest = a[0][0], largest = a[n - 1][n - 1]; ????if (x < smallest || x > largest) ????????return -1; ????int i = 0, j = n - 1; // set indexes for top right element ????while (i < n && j >= 0) { ????????if (mat[i][j] == x) { ????????????printf("\n Found at %d, %d", i, j); ????????????return 1; ????????} ????????if (mat[i][j] > x) ????????????j--; ????????else // if mat[i][j] < x ????????????i++; ????} ????printf("n Element not found"); ????return 0; // if ( i==n || j== -1 ) } // driver program to test above function int main() { ????int mat[4][4] = { ????????{ 10, 20, 30, 40 }, ????????{ 15, 25, 35, 45 }, ????????{ 27, 29, 37, 48 }, ????????{ 32, 33, 39, 50 }, ????}; ????search(mat, 4, 29); ????return 0; } ``` ## Java ``` // JAVA Code for Search in a row wise and // column wise sorted matrix class GFG { ????/* Searches the element x in mat[][]. If the? element is found, then prints its position? and returns true, otherwise prints "not found" and returns false */ ????private static void search(int[][] mat, int n, int x) ????{ ????????int i = 0, j = n - 1; // set indexes for top right ????????// element ????????while (i < n && j >= 0) { ????????????if (mat[i][j] == x) { ????????????????System.out.print("n Found at " + i + " " + j); ????????????????return; ????????????} ????????????if (mat[i][j] > x) ????????????????j--; ????????????else // if mat[i][j] < x ????????????????i++; ????????} ????????System.out.print("n Element not found"); ????????return; // if ( i==n || j== -1 ) ????} ????// driver program to test above function ????public static void main(String[] args) ????{ ????????int mat[][] = { { 10, 20, 30, 40 }, ????????????????????????{ 15, 25, 35, 45 }, ????????????????????????{ 27, 29, 37, 48 }, ????????????????????????{ 32, 33, 39, 50 } }; ????????search(mat, 4, 29); ????} } // This code is contributed by Arnav Kr. Mandal. ``` ## Python3 ``` # Python3 program to search an element? # in row-wise and column-wise sorted matrix # Searches the element x in mat[][]. If the? # element is found, then prints its position? # and returns true, otherwise prints "not found" # and returns false def search(mat, n, x): ????i = 0 ????# set indexes for top right element ????j = n - 1 ????while ( i < n and j >= 0 ): ????????if (mat[i][j] == x ): ????????????print("n Found at ", i, ", ", j) ????????????return 1 ????????if (mat[i][j] > x ): ????????????j -= 1 ????????# if mat[i][j] < x ????????else:? ????????????i += 1 ????print("Element not found") ????return 0 # if (i == n || j == -1 ) # Driver Code mat = [ [10, 20, 30, 40], ????????[15, 25, 35, 45], ????????[27, 29, 37, 48], ????????[32, 33, 39, 50] ] search(mat, 4, 29) # This code is contributed by Anant Agarwal. ``` ## C# ``` // C# Code for Search in a row wise and // column wise sorted matrix using System; class GFG { ????/* Searches the element x in mat[][]. If the? ????element is found, then prints its position? ????and returns true, otherwise prints "not found" ????and returns false */ ????private static void search(int[, ] mat, ???????????????????????????????int n, int x) ????{ ????????// set indexes for top right ????????// element ????????int i = 0, j = n - 1; ????????while (i < n && j >= 0) { ????????????if (mat[i, j] == x) { ????????????????Console.Write("n Found at " ??????????????????????????????+ i + ", " + j); ????????????????return; ????????????} ????????????if (mat[i, j] > x) ????????????????j--; ????????????else // if mat[i][j] < x ????????????????i++; ????????} ????????Console.Write("n Element not found"); ????????return; // if ( i==n || j== -1 ) ????} ????// driver program to test above function ????public static void Main() ????{ ????????int[, ] mat = { { 10, 20, 30, 40 }, ????????????????????????{ 15, 25, 35, 45 }, ????????????????????????{ 27, 29, 37, 48 }, ????????????????????????{ 32, 33, 39, 50 } }; ????????search(mat, 4, 29); ????} } // This code is contributed by Sam007 ``` ## PHP ``` <?php? // PHP program to search an? // element in row-wise and? // column-wise sorted matrix /* Searches the element $x? in mat[][]. If the element is? found, then prints its position? and returns true, otherwise prints "not found" and returns false */ function search(&$mat, $n, $x) { ????$i = 0; ????$j = $n - 1; // set indexes for ????????????????// top right element ????while ($i < $n && $j >= 0) ????{ ????????if ($mat[$i][$j] == $x) ????????{ ????????????echo "n found at " . $i.? ????????????????????????", " . $j; ????????????return 1; ????????} ????????if ($mat[$i][$j] > $x) ????????????$j--; ????????else // if $mat[$i][$j] < $x ????????????$i++; ????} ????echo "n Element not found"; ????return 0; // if ( $i==$n || $j== -1 ) } // Driver Code $mat = array(array(10, 20, 30, 40), ????????????array(15, 25, 35, 45), ????????????array(27, 29, 37, 48), ????????????array(32, 33, 39, 50)); search($mat, 4, 29); // This code is contributed // by ChitraNayal ?> ``` **輸出**： ``` Found at 2, 1 ``` * **復雜度分析**： * **時間復雜度**：`O(n)`。僅需要一個遍歷，即 i 從 0 到 n，j 從 n-1 到 0，最多 2 * n 步。 *上述方法也適用于 m x n 矩陣（不僅適用于 n x n）。復雜度為 O（m + n）。* * **空間復雜度**：`O(1)`。不需要多余的空間。 **相關文章**： [排序矩陣中的搜索元素](https://www.geeksforgeeks.org/search-element-sorted-matrix/) 如果您發現上述代碼/算法有誤，請寫評論，或者找到其他解決相同問題的方法。