时间戳

首页 > 解决方案 > 在“循环排序”二维数组中搜索元素

java - 在“循环排序”二维数组中搜索元素

问题描述

在过去的几天里，我一直在尝试找到一种方法来有效地对这种数组进行二进制搜索，并让它在任何给定的这种二维数组上工作。

说明：在本题中，您将参考二次二维数组，即行数和列数等于行数和列数等于n。将拆分定义为 n/2 大小的四分之四，如下所示： 阵列的插图

给定这种数组，我被要求搜索具有对数时间复杂度的元素，如果找到，我应该打印数组中元素的行和列。

有人对此有解决方案吗？一个完整的解决方案将是惊人的，但任何答案将不胜感激。

我将分享一段非常混乱的代码，但这是我到目前为止的工作，它适用于大多数数组元素，这还不够好，因为这意味着整个逻辑是错误的。

int[][] mat = {
            {1, 2, 3, 4, 17, 18, 19, 20},
            {8, 7, 6, 5, 24, 23, 22, 21},
            {12, 11, 10, 9, 28, 27, 26, 25},
            {16, 15, 14, 13, 32, 31, 30, 29},
            {49, 50, 51, 52, 33, 34, 35, 36},
            {56, 55, 54, 53, 40, 39, 38, 37},
            {60, 59, 58, 57, 45, 46, 41, 42},
            {64, 63, 62, 61, 48, 47, 44, 43}};
public static boolean search(int[][] mat, int num) {
    int n = mat.length;
    int i = 0;
    int j = 0;
    int[] indic = {-1, -1};
    if (num > mat[n - 1][0] || num < mat[0][0]) {
        return false;
    }
    while (n > 1) {
        int minS1 = mat[i][j];
        int maxS1 = mat[(n / 2) - 1 + i][j];
        int minS2 = mat[i][(n / 2) + j];
        int maxS2 = mat[(n / 2) - 1 + i][(n / 2) + j];
        int minS3 = mat[(n / 2) + i][(n / 2) + j];
        int maxS3 = mat[(n - 1) + i][(n / 2) + j];

        int minS4 = mat[(n / 2) + i][j];
        int maxS4 = mat[(n - 1) + i][j];
        checkSquare(num, n, indic, i, j, minS1, minS2, minS3, minS4, maxS1, maxS2, maxS3, maxS4);
        if (indic[0] != -1 && indic[1] != -1) {
            System.out.println("num=" + num);
            System.out.println("row=" + indic[0]);
            System.out.println("col=" + indic[1]);
            return true;
        }
        boolean x = false;
        if (num > maxS2) {
            if (num > maxS3) {
                i += n / 2;
            } else {
                if (n <= mat.length / 2 && i <= (n / 2)) {
                    x = true;
                    i += 1;
                    j += 1;
                } else {
                    if (i >= n / 2 && j < n / 2 && ((i < n) && (j < n))) {
                        i += 1;
                        j += 1;
                    } else {

                        System.out.println(minS1);
                        System.out.println(minS2);
                        System.out.println(minS3);
                        i += 1;
                        j += 1;
                    }
                }
            }
        } else {
            if (num > maxS1) {
                j += n / 2;
            } else {

                if (num > minS2) {
                    if (j > (mat.length / 2))
                        j = 0;
                    j += 1;
                    x = true;
                } else j += 1;
            }
        }
        if (num == mat[i][j]) {
            System.out.println("num=" + num);
            System.out.println("row=" + i);
            System.out.println("col=" + j);
            return true;
        }
        if (!x)
            n = (n / 2);
    }
    return false;
}

标签： javaarrayssorting

解决方案

根据您提供的图片，我认为您提供的二维数组不正确。较高象限中的所有值（顺时针编号，从左上角开始）需要大于下象限中的所有值。并且此规则也适用于所有子数组，直到达到 1x1 的大小。例如：

元素 24 位于位置 2-1-3，即第二主象限的第一子象限中的位置 3。

同样，元素 19 放置在位置 2-2-1，所以在 2-1-3 之后

我希望我理解正确。

编辑：

以下是我将如何进行。我会让你自己找出缺失的部分。首先，定义一个返回象限边界的函数：

int[][] getQuadrantBounds(int iMin, int iMax, int jMin, int jMax){...}

让这个函数返回一个 int[4][4]。它包含iMin, iMax, jMin, jMax四个象限。

然后检查第三象限中的最小元素是否大于或小于或等于num。请记住，任何象限中的最小元素始终位于[jMin][iMin]或[iMin][jMin]取决于您的实现。

之后，您就知道该元素是在 1,2 象限还是 3,4 象限中。重复该过程，但将其调整为两个象限。现在你知道在哪个象限了num。

当然，您在 while 循环中完成了所有这些操作，例如：

while(iMax - iMin > 0){ 
    int[][] quadrants = getQuadrantBounds(iMin, iMax, jMin, jMax);
    //TODO find first element in third quadrant
    //TODO nested if statements
    //TODO update iMin, iMax, jMin, jMax accordingly inside if statements
}

重复直到找到或直到不再给出 while 条件。

可能还有很大的改进空间，但这应该会给 O(log_2(n)) 执行时间。

推荐阅读