Рубрики

Поиск в отсортированном по строке и по столбцам двумерном массиве с использованием алгоритма «разделяй и властвуй»

Имеется матрица nxn, где каждая строка и столбец сортируются в порядке возрастания. Учитывая ключ, как решить, находится ли этот ключ в матрице.
Линейная сложность по времени обсуждается в предыдущем посте. Эта проблема также может быть очень хорошим примером для алгоритмов «разделяй и властвуй» . Ниже приводится алгоритм разделяй и властвуй.

1) Найти средний элемент.
2) Если средний элемент такой же, как возврат ключа.
3) Если средний элемент меньше ключа, тогда
… .3a) поиск подматрицы в нижней части среднего элемента
… .3b) Поиск подматрицы в правой части среднего элемента
4) Если средний элемент больше ключа, тогда
… .4a) поиск вертикальной подматрицы в левой части среднего элемента
… .4b) поиск подматрицы справа.

Следующая реализация Java вышеупомянутого алгоритма.

Джава

// Java-программа для реализации алгоритма разделяй и властвуй
// найти данный ключ в отсортированном по строке и столбцу двумерном массиве

class SearchInMatrix

{

    public static void main(String[] args)

    {

        int[][] mat = new int[][] { {10, 20, 30, 40}, 

                                    {15, 25, 35, 45},

                                    {27, 29, 37, 48},

                                    {32, 33, 39, 50}};

        int rowcount = 4,colCount=4,key=50;

        for (int i=0; i<rowcount; i++)

          for (int j=0; j<colCount; j++)

             search(mat, 0, rowcount-1, 0, colCount-1, mat[i][j]);

    }

  

    // Метод «разделяй и властвуй» для поиска заданного ключа в mat []

    // в строках от fromRow до toRow и столбцах от fromCol до

    // toCol

    public static void search(int[][] mat, int fromRow, int toRow, 

                              int fromCol, int toCol, int key)

    {

        // Найти среднее и сравнить со средним

        int i = fromRow + (toRow-fromRow )/2;

        int j = fromCol + (toCol-fromCol )/2;

        if (mat[i][j] == key) // Если ключ присутствует посередине

          System.out.println("Found "+ key + " at "+ i + 

                               " " + j);

        else

        {

            // правая четверть матрицы ищется во всех случаях.

            // Если он отличается от текущего вызова

            if (i!=toRow || j!=fromCol)

             search(mat,fromRow,i,j,toCol,key);

  

            // Особый случай для итерации с матрицей 1 * 2

            // mat [i] [j] и mat [i] [j + 1] - это только два элемента.

            // Так что просто проверьте второй элемент

            if (fromRow == toRow && fromCol + 1 == toCol)

              if (mat[fromRow][toCol] == key)

                System.out.println("Found "+ key+ " at "

                                   fromRow + " " + toCol);

  

            // Если средний ключ меньше, ищите нижнюю горизонталь

            // матрица и правая матрица

            if (mat[i][j] < key)

            {

                // ищем нижнюю горизонталь, если такая матрица существует

                if (i+1<=toRow)

                  search(mat, i+1, toRow, fromCol, toCol, key);

            }

  

            // Если средняя клавиша больше, то искать влево по вертикали

            // матрица и правая матрица

            else

            {

                // ищем левую вертикаль, если такая матрица существует

                if (j-1>=fromCol)

                  search(mat, fromRow, toRow, fromCol, j-1, key);

            }

        }

    }

}

C #

// C # программа для реализации
// разделяй и властвуй алгоритм
// найти заданный ключ построчно
// и отсортированный по столбцам 2D массив

using System;

  

public class SearchInMatrix

{

    public static void Main(String[] args)

    {

        int[,] mat = new int[,] { {10, 20, 30, 40}, 

                                    {15, 25, 35, 45},

                                    {27, 29, 37, 48},

                                    {32, 33, 39, 50}};

        int rowcount = 4, colCount = 4, key = 50;

        for (int i = 0; i < rowcount; i++)

            for (int j = 0; j < colCount; j++)

            search(mat, 0, rowcount - 1, 0, colCount - 1, mat[i, j]);

    }

  

    // Метод разделяй и властвуй

    // ищем данный ключ в mat []

    // в строках от fromRow до toRow

    // и столбцы из fromCol в

    // toCol

    public static void search(int[,] mat, int fromRow, int toRow, 

                            int fromCol, int toCol, int key)

    {

        // Найти среднее и сравнить со средним

        int i = fromRow + (toRow-fromRow )/2;

        int j = fromCol + (toCol-fromCol )/2;

        if (mat[i, j] == key) // Если ключ присутствует посередине

        Console.WriteLine("Found "+ key + " at "+ i + 

                            " " + j);

        else

        {

            // правая четверть матрицы ищется во всех случаях.

            // Если он отличается от текущего вызова

            if (i != toRow || j != fromCol)

            search(mat, fromRow, i, j, toCol, key);

  

            // Особый случай для итерации с матрицей 1 * 2

            // mat [i] [j] и mat [i] [j + 1] - это только два элемента.

            // Так что просто проверьте второй элемент

            if (fromRow == toRow && fromCol + 1 == toCol)

            if (mat[fromRow,toCol] == key)

                Console.WriteLine("Found "+ key + " at "

                                fromRow + " " + toCol);

  

            // Если средний ключ меньше, ищите нижнюю горизонталь

            // матрица и правая матрица

            if (mat[i, j] < key)

            {

                // ищем нижнюю горизонталь, если такая матрица существует

                if (i + 1 <= toRow)

                search(mat, i + 1, toRow, fromCol, toCol, key);

            }

  

            // Если средняя клавиша больше, то искать влево по вертикали

            // матрица и правая матрица

            else

            {

                // ищем левую вертикаль, если такая матрица существует

                if (j - 1 >= fromCol)

                search(mat, fromRow, toRow, fromCol, j - 1, key);

            }

        }

    }

}

  
// Этот код предоставлен 29AjayKumar


Выход:

Found 10 at 0 0
Found 20 at 0 1
Found 30 at 0 2
Found 40 at 0 3
Found 15 at 1 0
Found 25 at 1 1
Found 35 at 1 2
Found 45 at 1 3
Found 27 at 2 0
Found 29 at 2 1
Found 37 at 2 2
Found 48 at 2 3
Found 32 at 3 0
Found 33 at 3 1
Found 39 at 3 2
Found 50 at 3 3

Сложность времени:
Нам дана матрица * n, алгоритм можно рассматривать как повторяющийся для 3 матриц размера n / 2 xn / 2. Ниже приводится повторение сложности времени

 T(n) = 3T(n/2) + O(1) 

Решением повторения является O (n 1,58 ) с использованием Master Method .
Но фактическая реализация требует одну подматрицу размера nxn / 2 или n / 2 xn и другую подматрицу размера n / 2 xn / 2.

Эта статья предоставлена Каушик Леле . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Поиск в отсортированном по строке и по столбцам двумерном массиве с использованием алгоритма «разделяй и властвуй»

0.00 (0%) 0 votes