Рубрики

Поиск по строке и столбцу отсортированной матрицы

Учитывая матрицу nxn и число x, найдите положение x в матрице, если оно присутствует в ней. В противном случае выведите «Not Found». В данной матрице каждая строка и столбец сортируются в порядке возрастания. Разработанный алгоритм должен иметь линейную сложность по времени.

Пример :

Input : mat[4][4] = { {10, 20, 30, 40},
                      {15, 25, 35, 45},
                      {27, 29, 37, 48},
                      {32, 33, 39, 50}};
              x = 29
Output : Found at (2, 1)

Input : mat[4][4] = { {10, 20, 30, 40},
                      {15, 25, 35, 45},
                      {27, 29, 37, 48},
                      {32, 33, 39, 50}};
              x = 100
Output : Element not found

Простое решение — искать один за другим. Временная сложность этого решения составляет O (n 2 ).

Лучшее решениеиспользовать Divide и Conquer, чтобы найти элемент . Временная сложность этого решения составляет O (n 1,58 ). Пожалуйста, обратитесь к этой статье за подробностями.

Ниже приведено эффективное решение, которое работает за время O (n).
Прежде чем перейти к решению, давайте попробуем понять концепцию, которая фактически позволяет нам решать проблему за линейное время.
Начнем наш поиск с правого верхнего угла массива. Есть три возможных случая.

  1. Номер, который мы ищем, больше текущего номера. Это гарантирует, что все элементы в текущей строке меньше, чем искомое число, так как мы уже находимся на крайнем правом элементе, и строка отсортирована. Таким образом, вся строка удаляется, и мы продолжаем поиск в следующей строке. Здесь исключение означает, что мы не будем искать в этой строке снова.
  2. Номер, который мы ищем, меньше текущего номера. Это обеспечит, что все элементы в текущем столбце больше, чем число, которое мы ищем. Таким образом, весь столбец удаляется, и мы продолжаем поиск по предыдущему столбцу, то есть по столбцу слева.
  3. Номер, который мы ищем, равен текущему номеру. Это закончит наш поиск.

Поскольку на каждом шаге мы исключаем всю строку или столбец, временная сложность поиска становится равной O (n).

Мы также можем начать с левого нижнего угла матрицы.

Let x = element we’re trying to search for in the matrix,
….e = current element we’re processing in the array.

1) Start with top right element.
2) Loop: compare this element e with x
…i) if e = x, then return position of e, since we found x in the given matrix.
…ii) if e > x then move left to check elements smaller than e (if out of bound of matrix, then break and return false)
…iii) if e < x then move below to check elements greater than e (if out of bound of matrix, then break and return false)
3) repeat the i), ii) and iii) until you find the element or return false

Спасибо devendraiiit за предложенный ниже подход.

Реализация:

C ++

// C ++ программа для поиска элемента по строкам
// и отсортированная по столбцам матрица
#include <bits/stdc++.h>

  

using namespace std;

  
/ * Поиск элемента x в mat [] []. Если
элемент найден, затем печатается его позиция
и возвращает true, в противном случае выводится сообщение «not found»
и возвращает ложь * /

int search(int mat[4][4], int n, int x)

{

    if (n == 0)

        return -1;

    int smallest = a[0][0], largest = a[n - 1][n - 1];

    if (x < smallest || x > largest)

        return -1;

    // устанавливаем индексы для верхнего правого элемента

    int i = 0, j = n - 1; 

    while (i < n && j >= 0) {

        if (mat[i][j] == x) {

            cout << "n Found at "

                 << i << ", " << j;

            return 1;

        }

        if (mat[i][j] > x)

            j--;

        else // если mat [i] [j] <x

            i++;

    }

  

    cout << "n Element not found";

    return 0; // если (i == n || j == -1)

}

  
// Код драйвера

int main()

{

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

                      { 15, 25, 35, 45 },

                      { 27, 29, 37, 48 },

                      { 32, 33, 39, 50 } };

    search(mat, 4, 29);

  

    return 0;

}

  
// Этот код добавлен
// Аканкша Рай (Abby_akku)

С

// C программа для поиска элемента по строкам
// и отсортированная по столбцам матрица
#include <stdio.h>

  
/ * Поиск элемента x в mat [] []. Если
элемент найден, затем печатается его позиция
и возвращает true, в противном случае выводится сообщение «not found»
и возвращает ложь * /

int search(int mat[4][4], int n, int x)

{

    if (n == 0)

        return -1;

    int smallest = a[0][0], largest = a[n - 1][n - 1];

    if (x < smallest || x > largest)

        return -1;

    int i = 0, j = n - 1; // устанавливаем индексы для верхнего правого элемента

    while (i < n && j >= 0) {

        if (mat[i][j] == x) {

            printf("\n Found at %d, %d", i, j);

            return 1;

        }

        if (mat[i][j] > x)

            j--;

        else // если mat [i] [j] <x

            i++;

    }

  

    printf("n Element not found");

    return 0; // если (i == n || j == -1)

}

  
// программа драйвера для проверки вышеуказанной функции

int main()

{

    int mat[4][4] = {

        { 10, 20, 30, 40 },

        { 15, 25, 35, 45 },

        { 27, 29, 37, 48 },

        { 32, 33, 39, 50 },

    };

    search(mat, 4, 29);

    return 0;

}

Джава

// JAVA-код для поиска в ряд и
// отсортированная по столбцам матрица

  

class GFG {

  

    / * Поиск элемента x в mat [] []. Если

элемент найден, затем печатается его позиция
и возвращает true, в противном случае выводится сообщение «not found»
и возвращает ложь * /

    private static void search(int[][] mat, int n, int x)

    {

  

        int i = 0, j = n - 1; // устанавливаем индексы для верхнего правого

        // элемент

  

        while (i < n && j >= 0) {

            if (mat[i][j] == x) {

                System.out.print("n Found at " + i + " " + j);

                return;

            }

            if (mat[i][j] > x)

                j--;

            else // если mat [i] [j] <x

                i++;

        }

  

        System.out.print("n Element not found");

        return; // если (i == n || j == -1)

    }

    // программа драйвера для проверки вышеуказанной функции

    public static void main(String[] args)

    {

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

                        { 15, 25, 35, 45 },

                        { 27, 29, 37, 48 },

                        { 32, 33, 39, 50 } };

  

        search(mat, 4, 29);

    }

}
// Этот код предоставлен Арнавом Кр. Мандал.

python3

# Python3 программа для поиска элемента
# в построчном и по столбцам отсортированной матрице

  
# Ищет элемент x в mat [] []. Если
# элемент найден, затем печатает его позицию
# и возвращает true, в противном случае выводится «not found»
# и возвращает false

def search(mat, n, x):

  

    i = 0

      

    # установить индексы для верхнего правого элемента

    j = n - 1

    while ( i < n and j >= 0 ):

      

        if (mat[i][j] == x ):

      

            print("n Found at ", i, ", ", j)

            return 1

      

        if (mat[i][j] > x ):

            j -= 1

              

        # if mat [i] [j] <x

        else

            i += 1

      

    print("Element not found")

    return 0 # if (i == n || j == -1)

  
Код водителя

mat = [ [10, 20, 30, 40],

        [15, 25, 35, 45],

        [27, 29, 37, 48],

        [32, 33, 39, 50] ]

search(mat, 4, 29)

  
# Этот код предоставлен Anant Agarwal.

C #

// Код C # для поиска в строке и
// отсортированная по столбцам матрица

using System;

  

class GFG {

    / * Поиск элемента x в mat [] []. Если

    элемент найден, затем печатается его позиция

    и возвращает true, в противном случае выводится сообщение «not found»

    и возвращает ложь * /

    private static void search(int[, ] mat,

                               int n, int x)

    {

        // устанавливаем индексы для верхнего правого

        // элемент

        int i = 0, j = n - 1;

  

        while (i < n && j >= 0) {

            if (mat[i, j] == x) {

                Console.Write("n Found at "

                              + i + ", " + j);

                return;

            }

  

            if (mat[i, j] > x)

                j--;

            else // если mat [i] [j] <x

                i++;

        }

  

        Console.Write("n Element not found");

        return; // если (i == n || j == -1)

    }

    // программа драйвера для проверки вышеуказанной функции

    public static void Main()

    {

  

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

                        { 15, 25, 35, 45 },

                        { 27, 29, 37, 48 },

                        { 32, 33, 39, 50 } };

  

        search(mat, 4, 29);

    }

}

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

PHP

<?php 
// PHP программа для поиска
// элемент по строкам и
// отсортированная по столбцам матрица

  
/ * Поиск элемента $ x
в мате [] []. Если элемент
найден, затем печатает свою позицию
и возвращает истину, иначе печатает
"not found" и возвращает false * /

function search(&$mat, $n, $x)

{

    $i = 0;

    $j = $n - 1; // устанавливаем индексы для

                // верхний правый элемент

    while ($i < $n && $j >= 0)

    {

        if ($mat[$i][$j] == $x)

        {

            echo "n found at " . $i

                        ", " . $j;

            return 1;

        }

        if ($mat[$i][$j] > $x)

            $j--;

        else // если $ mat [$ i] [$ j] <$ x

            $i++;

    }

      

    echo "n Element not found";

    return 0; // если ($ i == $ n || $ j == -1)

}

  
// Код драйвера

$mat = array(array(10, 20, 30, 40),

            array(15, 25, 35, 45),

            array(27, 29, 37, 48),

            array(32, 33, 39, 50));

search($mat, 4, 29);

  
// Этот код добавлен
// ChitraNayal
?>

Выход :

Found at 2, 1

Сложность времени: O (n)

Вышеуказанный подход также будет работать для матрицы mxn (не только для nxn). Сложность будет O (m + n).

Связанная статья:
Поиск элемента в отсортированной матрице

Пожалуйста, напишите комментарии, если вы обнаружите, что приведенные выше коды / алгоритмы неверны, или найдете другие способы решения той же проблемы.

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

Поиск по строке и столбцу отсортированной матрицы

0.00 (0%) 0 votes