java二维数组查找

全栈程序员-站长 • 2022年5月30日下午4:16 • 未分类 • 阅读 31

大家好，又见面了，我是你们的朋友全栈君。

问题：在一个二维数组中，每行每列都递增排序，在这个数组中查找一个数字，如果存在返回true，否则返回flase。

分析：数组查找一直都是初学java的同学的热门考点，关于查找主要有顺序查找、二分查找、哈希表查找、二叉排序树查找。

我们看下下面这个数组，数组满足每行每列都是递增顺序。在这个数组中查找某个数，如果存在，返回true和所在位置。否则返回flase。

java二维数组查找

这里我们该选择什么样的方式来查找呢，首先排除顺序查找，顺序查找是大部分人都应该会的，这里不需要做太多介绍。

然后通过数组特性分析，一个排序好的数组，我们首先考虑二分法，如果数组中选取的数字和要查找的数字相等时，查找结束。如果选取的数字大于要查找的数字。那么根据数组要求，所查找数字位于选取数字的左边和上边（图）。反之就是在右边或下边（图2）

java二维数组查找

可以看到，这样方法中，由于要查找的数字相对于当前选取的位置有可能在两个区域中出现，而且这两个区域还有重叠的部分，这样问题看起来就复杂了，于是很多人卡住这里束手无策。为什么会遇到这种难题呢，是因为我们选取的数是二维数组中间的数字。如果我们从数组的一个角上来选取一个数会不会变得简单点呢？还是上图的例子。我们来看一下。首先我们选取数组右上角的9，有三种情况：
1）要查找的数等于9，查找结束。

2）要查找的数字大于9，那么9所在的这一行就可以排除了，因为从这个数组的特征可以看到9就是这一行的最大数。最大数都小于要查找的数字，那这一行当然不可能等于要查找的数。所查找的数字在剩下的区域（图3）。

3）要查找的数小于9，那么9所在的这一列可以排除，因为9所在这一列中9是最小的数字。同理，查找的数字在剩下的区域（图4）。

java二维数组查找

通过上一步。我们可以得到一个新的4×3或者3×4的数组。对新的数组继续执行上述步骤。直到数组变为0x0。即表明数组中没有我们要查找的数字。以上就是我们的思路。具体代码实现如下：

package array;
public class FindInPartiallySortedMatrix {
    private int row, col;
    private boolean isFind;
    public FindInPartiallySortedMatrix Find(int[][] a,int find){
        int rows = a.length-1,cols = a[0].length-1,firstrows = 0;
        if(rows<=0||cols<=0){
            System.out.println("数组为空，无任何数据");
        }
        else{
            isFind = false;
            while (firstrows<=rows&&cols>=0){
                if(a[firstrows][cols]>find){
                    --cols;
                }
                else if(a[firstrows][cols]<find){
                    ++firstrows;
                }
                else {
                    this.row = firstrows;
                    this.col = cols;
                    this.isFind = true;
                    break;
                }
            }
        }
            System.out.println(this.isFind + " " + this.row + " " + this.col);
        return this;
    }
  public static void main(String[] args){
      int[][] a ={
  
  {1,2,8,4},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
      FindInPartiallySortedMatrix finds = new FindInPartiallySortedMatrix();
      finds.Find(a,1);
      finds.Find(a,7);
      finds.Find(a,13);
      finds.Find(a,15);
      finds.Find(a,3);
      //System.out.println(finds.isFind+" "+finds.row+" "+finds.col);
}
}

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/138945.html原文链接：https://javaforall.net