使用未排序的行在2d数组中搜索为O（n） [英] searching in 2d array as O(n) with unsorted rows

问题描述

我需要编写一个方法，该方法采用2d数组'int [] [] m'和值'val'并检查val是否在数组中的复杂度为O（n），而n定义为行数和m必须是平方

I need to write a method that takes 2d array 'int [][] m' and a value 'val' and check if val is in the array in the complexity of O(n) while n defined as the number of rows and m must be squared

可以用作我方法参数的数组必须为此方法返回true：

The array that can use as a parameter for my method must return true for this method:

（如果它返回true则所以数组是按要求的）

(if it returns true so the array is as requested)

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在数组中，看起来像这样：

My method should return true if val is in the array and looks like this:

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

推荐答案

iff可能。矩阵 m 是一个大小为 n x n 的方阵。核心理念的灵感来自 oleg.cherednik的回答。一旦我们在 m 中找到行，那么 m [row] [0 ]> = val ，我们知道 val 必须在行行中或 row - 1 （因为行上的相同比较 - 1 是 false ）。因此，我们必须找到我们的候选行（ O（n）），然后只分析这两行（也 O（n））。如果 m 不是方形，而是矩形，则算法的复杂度为 O（n + k），其中 n 是行数， k 是 m 中的列数。这导致了以下算法。

It is possible iff. the matrix m is a square matrix of size n x n. Core idea is inspired by oleg.cherednik's answer. As soon as we find a row in m, such that m[row][0] >= val, we know that val must be in either row row or row - 1(since the same comparison on row - 1 was false). Thus, we have to find our candidate rows (O(n)) and then analyze only those two rows (also O(n)). If m is not square, but rectangular, the algorithm has a complexity of O(n + k), where n is the number of rows and k is the number of colums in m. This leads to the following algorithm.

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（log（n））而不是 O（n）中找到候选行。对于方形矩阵，渐近运行时仍然是 O（n），对于非正方形 nxk 矩阵， O（log（n）+ k） 。这个想法取自 Saeed Bolhasani的回答。

We can improve the acutal runtime by determining the candidate lines through a binary search algorithm so that candidate lines are found in O(log(n)) instead of O(n). The asymptotical runtime will still be O(n) for square matrices and O(log(n) + k) for non-square n x k matrices. The idea for this was taken from 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;
  }

这篇关于使用未排序的行在2d数组中搜索为O（n）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！