java - 在二维排序数组中搜索元素
问题描述
我必须编写一个代码(作为练习),它接收一个二维(方形)按行和按列排序的数组和一个元素,如果元素存在于数组中,则返回 true。
当我听到“排序”时首先想到的是二分搜索,但我意识到每一行中的最后一个元素不一定小于下一行中的第一个元素。
所以,我发现最好的复杂度是 O(n),并编写了以下代码:
public static boolean findN(int[][] a, int x) {
if (a.length == 0 || a[0].length == 0 || x > a[a.length - 1][a[0].length - 1] || x < a[0][0]) {
return false;
}
int LastRow = a.length - 1, Lastcol = a[0].length - 1, row = 0, col = 0;
while (row <= LastRow) {
if (a[row][col] == x) {
return true;
} else if (col < Lastcol) {
col++;
} else {
col = 0;
row++;
}
}
return false;
}
数组示例:
int [] [] arr = {{1,2,7,30}
{2,4,18,50}
{3,6,19,90}
{4,7,20,91}}
- 在意识到最好的复杂性是 O(n) 之后,我用谷歌搜索了这个问题,所以我几乎可以肯定我是对的(尽管有些人声称他们可以在 O(log(n)) 中做到这一点),但是我真的吗?
- 欢迎任何其他想法和改进,提前谢谢大家!
解决方案
几个月前我遇到了一个类似的问题,这是我发现在 O(logN + logM) 中工作的代码 [假设数组是按行和按列排序的]。
[...] 但我意识到每行中的最后一个元素不一定小于下一行中的第一个元素。- 在这种情况下,您无法实现 O(logn) 复杂度。
简单的二分搜索:
static void binarySearch(int mat[][], int i, int j_low, int j_high, int x) {
while (j_low <= j_high) {
int j_mid = (j_low + j_high) / 2;
// Element found
if (mat[i][j_mid] == x) {
System.out.println ( "Found at (" + i + ", " + j_mid +")");
return;
}
else if (mat[i][j_mid] > x)
j_high = j_mid - 1;
else
j_low = j_mid + 1;
}
System.out.println ( "Element no found");
}
核心逻辑:
static void sortedMatrixSearch(int mat[][], int n, int m, int x) {
// Single row matrix
if (n == 1) {
binarySearch(mat, 0, 0, m - 1, x);
return;
}
// Do binary search in middle column.
// Condition to terminate the loop when the
// 2 desired rows are found
int i_low = 0;
int i_high = n - 1;
int j_mid = m / 2;
while ((i_low + 1) < i_high) {
int i_mid = (i_low + i_high) / 2;
// element found
if (mat[i_mid][j_mid] == x) {
System.out.println ( "Found at (" + i_mid +", " + j_mid +")");
return;
}
else if (mat[i_mid][j_mid] > x)
i_high = i_mid;
else
i_low = i_mid;
}
// If element is present on
// the mid of the two rows
if (mat[i_low][j_mid] == x)
System.out.println ( "Found at (" + i_low + "," + j_mid +")");
else if (mat[i_low + 1][j_mid] == x)
System.out.println ( "Found at (" + (i_low + 1) + ", " + j_mid +")");
// Ssearch element on 1st half of 1st row
else if (x <= mat[i_low][j_mid - 1])
binarySearch(mat, i_low, 0, j_mid - 1, x);
// Search element on 2nd half of 1st row
else if (x >= mat[i_low][j_mid + 1] && x <= mat[i_low][m - 1])
binarySearch(mat, i_low, j_mid + 1, m - 1, x);
// Search element on 1st half of 2nd row
else if (x <= mat[i_low + 1][j_mid - 1])
binarySearch(mat, i_low + 1, 0, j_mid - 1, x);
// search element on 2nd half of 2nd row
else
binarySearch(mat, i_low + 1, j_mid + 1, m - 1, x);
}
驱动方法:
public static void main (String[] args) {
int n = 4, m = 5, x = 8;
int mat[][] = {{0, 6, 8, 9, 11},
{20, 22, 28, 29, 31},
{36, 38, 50, 61, 63},
{64, 66, 100, 122, 128}};
sortedMatrixSearch(mat, n, m, x);
}
希望这可以帮助。祝你好运。
推荐阅读
- c# - 创建一个哈希集
动态的? - git - 为特定文件禁用 safecrlf
- javascript - Blazor Web 程序集不返回控制器中捕获的数据库行
- python - 正则表达式 - 使用 python 以特定格式提取三个数字
- c# - Azure Block Blob:提交以前提交的块时“指定的块列表无效”
- apache-spark - Spark 累加器线程安全和 .value() 性能
- html - 如何在 Google 站点中使用 iframe 显示 PHP 站点
- c++ - 将字符串转换为双精度数会保持舍入为整数
- math - “W4 方法”的实现(newton-raphson 扩展)
- wso2 - 是否可以监视/跟踪来自 WSO2 服务器的连接池