поиск в массиве 2d как O (n) с несортированными строками - PullRequest
Новая
       6

поиск в массиве 2d как O (n) с несортированными строками

0 голосов
/ 01 июня 2018

Мне нужно написать метод, который принимает 2d массив '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,},
};

Мой метод должен возвращать true, если val находится в массиве и выглядит следующим образом: 

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

Ответы [ 3 ]

0 голосов
/ 01 июня 2018

Возможно, еслиматрица m представляет собой квадратную матрицу размера nxn .Основная идея основана на ответе oleg.cherednik .Как только мы находим row в m, такой, что m[row][0] >= val, мы знаем, что val должно быть в любой строке row или row - 1 (поскольку такое же сравнение на row - 1 было false).Таким образом, мы должны найти строки-кандидаты ( O (n) ) и затем проанализировать только эти две строки (также O (n) ).Если m не квадратный, а прямоугольный, алгоритм имеет сложность O (n + k) , где n - количество строк и k * 1024.* - количество столбцов в m.Это приводит к следующему алгоритму: 

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) для квадратных матриц и O (log (n) + k) для неквадратных nxk матриц.Идея для этого была взята из ответа Саида Болхасани . 

  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;
  }
0 голосов
/ 01 июня 2018

ваше решение здесь.я сделал функцию, которая выполняет бинарный поиск по первому столбцу.если значение val находится в первом столбце, функция возвращает true, иначе последний период 'l' и 'r' будет для нас полезен.'r' и 'l' всегда равны или имеют только одно расстояние (r = l или abs (rl) = 1).нижняя граница 'r' и 'l' - ожидаемая строка, в которой может существовать val.поэтому мы должны искать эту строку.O (n) для двоичного поиска - Log (n), а для поиска строки - n.итоговый O (n) будет n.code здесь: 

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;
}
0 голосов
/ 01 июня 2018

Smth.как это.В случае Каждое число в строке i равно или меньше, чем каждое число в строке i+1, чем можно проверить только первый элемент в каждой строке, чтобы определить строку, где может быть требуемое значение.Элемент в несортированной строке можно найти только при полном сканировании.

Этот алгоритм должен сканировать только 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
...