java - 递归鞍背 - 在 Java 中搜索已排序的二维数组中的元素
问题描述
我在 Java 中的一个排序的 2D 数组中编写鞍背搜索,奇怪的事情发生了。
算法必须找到k
数组中给定元素的第一次出现(首先是行,然后是列)。然后它还应该显示在哪个索引上找到了给定的数字。
我迭代地编写了鞍背算法并且它可以工作,但是在将其重新编码为递归之后 - 它没有。
对于数组
10 10 10 10
10 20 20 30
20 20 20 40
和k: 20
它输出,在给定的数组中找不到 k。
此外 - 该算法的复杂度必须低于 O(n,m)^3,因此任何其他算法技巧都会受到赞赏。
这是我的代码:
static boolean RekPier(int tab[][], int i, int j, int m, int n, int k){
System.out.println(i + " " + j + " " + tab[i][j]);
if (tab[i][j] == k && i < m && j < n){
findex = i;
lindex = j;
return true;
}
else if((tab[i][j] > k || tab[i][n-1] < k) && (i < m && j < n)){
int i1 = i+1;
if(i1 == m) return false;
RekPier(tab, i1, 0, m, n, k);
}
else if (i < m && j < n){
int j1 = j+1;
if(j1 == n) return false;
RekPier(tab, i, j1, m, n, k);
}
return false;
}
解决方案
您的实现有一些错误,但我修改了函数,如下所示:
static int RekPier(int arr[][], int i, int j,int M ,int N,int Value)
{
// If the entire column is traversed
if (j >= M)
return 0;
// If the entire row is traversed
if (i >= N)
return 1;
if(arr[i][j] == Value){
System.out.println("Row:" +i +'\t' +"Column:" +j);
}
// Recursive call to traverse the matrix in the Horizontal direction
if (RekPier(arr, i,j + 1, M, N,Value) == 1)
return 1;
// Recursive call for changing the Row of the matrix
return RekPier(arr,i + 1,0, M, N,Value);
}
和你一样复杂
推荐阅读
- wpf - 更改主题时 WPF 发布的应用程序崩溃
- selenium - 无法通过 selenium-java 切换到 iframe 中的内部 html 代码
- javascript - 根据字段的值隐藏 Jquery 数据表中的自动生成按钮
- c# - Azure 文件存储:创建嵌套目录
- php - 我如何让这个策略在 Laravel 中起作用?
- javascript - 在 React 中导入外部 Javascript 文件会出错
- javascript - 在 FabricJS 中调整窗口大小时如何始终将剪切区域居中?
- python - 在python中将多列转换为行
- javascript - 如何访问数据对象中的数组?
- json.net - NServiceBus 没有反序列化消息