在未排序的行中，以O(n)时间复杂度在二维数组中搜索。

Question

我需要编写一个方法，它接受二维数组'int[][] m'和一个值 'val'并检查val是否在数组中，其时间复杂度为 O（n），其中n定义为行数，并且m必须为平方。

可以用作我的方法参数的数组必须对这个方法返回true：

(如果它返回true，那么数组符合要求)

public static boolean test(int[][] m) {
    int n = m.length;
    for (int r = 0; r < (n - 1); r++)
        for (int c = 0; c < n; c++)
            for (int i = 0; i < n; i++)
                if (m[r][c] > m[r + 1][i]) return false;
    return true;
}

这个数组返回TRUE：

int [][] arr3 = new int [][]{
    { 0,   2,    1,    2,   0,  5,   5,   5,  },
    { 21,  21,   7,    7,   7,  21,  21,  21 ,},
    { 21,  21,  21,   21,  21,  21,  21 , 21, },
    { 21,  21,  23 ,  42,  41,  23,  21,  21, },
    { 60  ,56,  57,   58,  53,  52,  47,  51 ,},
    { 61,  65,  70 ,  72,  73,  78,  82,  98 ,},
    { 112, 121, 112, 134, 123, 100,  98,  111,},
    { 136, 136, 136, 134, 147, 150,  154, 134,},
};

我的方法应该在数组中包含val并且像这样返回true:

public boolean findValTest(int [][] m, int val){...}

- t0nty

---

...并且*O(n)*被认为是最坏情况的执行时间？如果是这样，我有一种感觉这是不可能的。 - Turing85

你的 val 在哪里？ - oleg.cherednik

乍一看，每列都已排序，因此您可以获得每列的O(log n)，然后将其乘以列数以获得O(n log n)。但是，要达到O(n)？我很想阅读其他人的想法。 - Otomatonium

@Otomatonium 是的，这就是我想的...不知道该怎么办了... - t0nty

我认为O(n²)是你能做到的最好的。你必须检查每一列，如果这些列正确，就需要n次检查。也许有一些非常俗套的算法可以将其分解，但我不这么认为... - Dániel Somogyi

Answer 1

如果矩阵 m 是一个大小为 n x n 的方阵，则可能性才存在。核心思想受到了 oleg.cherednik's answer 的启发。一旦我们在矩阵 m 中找到一个 row，使得 m[row][0] >= val，我们就知道 val 必须在行 row 或行 row - 1 中（因为对于 row - 1 上的同样比较结果为 false）。因此，我们需要找到候选行（O(n)），然后只分析这两行（同样是 O(n)）。如果矩阵 m 不是方阵，而是长方形矩阵，则该算法的复杂度为 O(n + k)，其中 n 是行数，k 是列数。这导致了以下算法。

public class Test {

  public static boolean contains(final int[][]m, final int value) {
    int candidateRow = m.length;
    for (int row = 1; row < m.length; ++row) {
      if (m[row][0] == value) {
        return true;
      }
      if (m[row][0] > value) {
        candidateRow = row;
        break;
      }
    }

    for (int val : m[candidateRow - 1]) {
      if (val == value) {
        return true;
      }
    }

    if (candidateRow < m.length) {
      for (int val : m[candidateRow]) {
        if (val == value) {
          return true;
        }
      }
    }
    return false;
  }

  public static void main(String[] args) {
    int [][] testArray = new int [][]{
        {   0,   2,   1,   2,   0,   5,   5,   5 },
        {  21,  21,   7,   7,   7,  21,  21,  21 },
        {  21,  21,  21,  21,  21,  21,  21,  21 },
        {  21,  21,  23,  42,  41,  23,  21,  21 },
        {  60,  56,  57,  58,  53,  52,  47,  51 },
        {  61,  65,  70,  72,  73,  78,  82,  98 },
        { 112, 121, 112, 134, 123, 100,  98, 111 },
        { 136, 136, 136, 134, 147, 150, 154, 134 }
    };
    for (int[] row : testArray) {
      for (int val : row) {
        System.out.print(contains(testArray, val) + " ");
      }
      System.out.println();

    }
    System.out.println();
    System.out.println();
    final int[] notInMatrix = { -1, 3, 4, 6, 8, 22, 30, 59, 71, 113, 135 };
    for (int val : notInMatrix) {
      System.out.print(contains(testArray, val) + " ");
    }
    System.out.println();
  }
}

我们可以通过使用二分搜索算法确定候选行，从而将候选行的查找时间复杂度从 O(n) 降低到 O(log(n))，从而提高实际运行时间。对于方阵，渐近运行时间仍为 O(n)，对于非方阵的 n x k 矩阵，则为 O(log(n) + k)。这个想法来自于 Saeed Bolhasani's answer。

  private static int findCandidateRow(final int[][] m, final int value) {
    int lower = 0;
    int upper = m.length;
    int middle = (upper + 1) / 2;
    while (middle != m.length 
        && middle != 1
        && (m[middle][0] < value || m[middle - 1][0] > value)) {
      if (m[middle][0] < value) {
        lower = middle;
      } else {
        upper = middle;
      }
      middle = lower + (upper - lower + 1) / 2;
    }
    return middle;
  }

- Turing85

---

我可以问一下，为什么你每次都用++row而不是row++？ - t0nty

@MatanCohen 这是个人风格问题。对我来说，++i 是“更明显的操作”（先增加，再返回增加后的值）。因此，我默认使用前增量，只有在必要时才使用后增量。 - Turing85

我可以问一下给我点踩的人，是什么原因导致了这个踩吗？ - Turing85

Answer 2

类似于这样的情况。如果每一行中的每个数字都小于或等于下一行中的每个数字，那么您只需要检查每行的第一个元素即可确定所需值可能在哪一行。未排序行中的元素只能通过完全扫描找到。

该算法仅需扫描2行，时间复杂度为O(n)（其中n为行数）。

public static boolean findValTest(int[][] m, int val) {
    for (int row = 0; row < m.length; row++) {
        if (m[row][0] <= val && row != m.length - 1)
            continue;

        int r = row;

        while (r >= row - 1 && r >= 0) {
            for (int col = 0; col < m[r].length; col++)
                if (m[r][col] == val)
                    return true;

            r--;
        }

        return false;
    }

    return false;
}

测试用例：

System.out.println(findValTest(arr3, -1)); // false
System.out.println(findValTest(arr3, 5)); // true
System.out.println(findValTest(arr3, 7)); // true
System.out.println(findValTest(arr3, 55)); // false
System.out.println(findValTest(arr3, 47)); // true
System.out.println(findValTest(arr3, 147)); // true
System.out.println(findValTest(arr3, 200)); // false
System.out.println(findValTest(new int[][] { { 3, 4, 5 } }, 4));   // true

- oleg.cherednik

---

行未排序，遗憾地。 - t0nty

是的，但是“第i行的每个数字都小于或等于第i+1行的每个数字”。 - oleg.cherednik

这个算法对于 val=4, {{3,4,5}} 这种最小的情况也没有返回正确的值。 - Will M.

修改了问题，以使其更易理解。 - t0nty

@oleg.cherednik 实际上不太好用... 我试图找到7，但在我的测试器上返回了21。 - t0nty

Answer 3

您的解决方案在这里。我编写了一个函数，用于对第一列进行二分查找。如果在第一列中找到了val，则函数返回true，否则'l'和'r'的最后一个周期对我们有益。 'r'和'l'始终相等或仅有一个距离（r=l或abs（r-l）=1）。 'r'和'l'的下限是可能存在val的行。因此，我们应该搜索此行。
二分查找的O(n)是Log（n），行搜索的O(n)是n。因此，最终的O(n)将是n。代码如下：

static boolean binarySearch(int arr[][], int l, int r, int x)
{
    if (r>=l)
    {
        int mid = l + (r - l)/2;

        // If the element is present at the 
        // middle itself
        if (arr[mid][0] == x)
           return true;

        // If element is smaller than mid, then 
        // it can only be present in left subarray
        if (arr[mid][0] > x)
           return binarySearch(arr, l, mid-1, x);

        // Else the element can only be present
        // in right subarray
        return binarySearch(arr, mid+1, r, x);
    }

    // We reach here when element is not present
    //  in array

    int row = Math.min(l,r);
    for(int i=0; i<arr[0].length ;i++)
      if(arr[row][i]==x)
        return true;
    return false;
}

- Saeed Bolhasani