搜索按行和按列排序的矩阵
如果您想练习数据结构和算法程序，可以通过 数据结构和算法面试题.
如果您想练习数据结构和算法程序，可以通过 数据结构和算法面试题.
问题：
给定行和列的排序矩阵，我们需要以最小的时间复杂度来搜索元素。
解决方案：
解决方案1：
您可以简单地在2D矩阵中搜索元素，但是它将以O（R * C）复杂度完成。
解决方案2：
- 遍历每一行
- 除非找到元素，否则对行进行二进制搜索。
- 如果找不到该元素，则返回false。
时间复杂度：O（C * logR）
解决方案3：
我们将使用以下逻辑来搜索元素
- 元素对当前元素的权利将大于元素
- 保留到当前元素的元素将小于元素
- 直到当前元素的元素将大于元素
- 当前元素顶部的元素小于元素
算法：
- 从右上角的元素开始，因此初始化r = 0和c =
sortedMatrix [0] .length-1
-
在边界条件下遍历矩阵。
-
如果当前元素说m等于元素X，则将其返回。
-
如果m < X, go left,so decrease column by 1 (c--).
-
如果m > X, go right, so increase row by 1(r++).
时间复杂度：O（R + C）
爪哇程序以按行和按列排序的搜索矩阵：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
包 组织.Arpit.爪哇2blog; 上市 类 SearchElementInSortedMatrixMain { 上市 静态的 虚空 主要(串[] args) { 整型[][] sortedMatrix = { { 1, 6, 10, 12, 20 }, { 4, 8, 15, 22, 25 }, { 5, 20, 35, 37, 40 }, { 10, 28, 38, 45, 55 } }; 搜索ElementInSortedMatrix(sortedMatrix, 37); } 私人的 静态的 虚空 搜索ElementInSortedMatrix(整型[][] sortedMatrix, 整型 X) { 整型 R = sortedMatrix.长度; 整型 C = sortedMatrix[0].长度; 整型 r = 0, c = C - 1; //我们可以向左或向下走 //左=>减少列数，0将是边界 //下=>在行中增加，R-1将是边界 而 (r <= R - 1 && c >= 0) { 如果 (sortedMatrix[r][c] == X) { //找到元素 系统.出.打印(“元素位于r =“ + r + “ c =” + c); 返回; } 如果 (X < sortedMatrix[r][c]) { // 向左移动 c = c - 1; } 其他 { //下移 r = r + 1; } } 系统.出.打印(“在排序的矩阵中找不到元素”); } } |
运行该程序时，将获得以下输出：
|
1 2 3 |
元件 发现 在 r =2 c=3 |
