Рубрики

Найти общий элемент во всех строках данной отсортированной по строке матрицы

Дана матрица, в которой каждая строка отсортирована в порядке возрастания. Напишите функцию, которая находит и возвращает общий элемент во всех строках. Если общего элемента нет, возвращается -1.

Пример:

Input: mat[4][5] = { {1, 2, 3, 4, 5},
                    {2, 4, 5, 8, 10},
                    {3, 5, 7, 9, 11},
                    {1, 3, 5, 7, 9},
                  };
Output: 5

Простое решение O (m * n * n) состоит в том, чтобы взять каждый элемент первой строки и искать его во всех других строках, пока мы не найдем общий элемент. Временная сложность этого решения составляет O (m * n * n), где m — количество строк, а n — количество столбцов в данной матрице. Это можно улучшить до O (m * n * Logn), если мы используем бинарный поиск вместо линейного поиска.

Мы можем решить эту проблему за O (mn) время, используя подход, аналогичный Merge Sort . Идея состоит в том, чтобы начать с последнего столбца каждой строки. Если элементы во всех последних столбцах одинаковы, то мы нашли общий элемент. В противном случае мы найдем минимум всех последних столбцов. Как только мы находим минимальный элемент, мы знаем, что все остальные элементы в последних столбцах не могут быть общим элементом, поэтому мы уменьшаем индекс последнего столбца для всех строк, кроме строки, которая имеет минимальное значение. Мы продолжаем повторять эти шаги, пока либо все элементы в текущем последнем столбце не станут одинаковыми, либо индекс последнего столбца не достигнет 0.

Ниже приведена реализация вышеуказанной идеи.

C ++

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

using namespace std;

  
// Укажите количество строк и столбцов
#define M 4
#define N 5

  
// Возвращает общий элемент во всех строках mat [M] [N]. Если нет
// общий элемент, затем возвращается -1

int findCommon(int mat[M][N])

{

    // Массив для хранения индексов текущего последнего столбца

    int column[M];

    int min_row; // Хранить индекс строки, текущий

    // последний элемент минимальный

  

    // Инициализируем текущий последний элемент всех строк

    int i;

    for (i = 0; i < M; i++)

        column[i] = N - 1;

  

    min_row = 0; // Инициализируем min_row как первый ряд

  

    // Продолжаем находить min_row в текущем последнем столбце, пока либо

    // все элементы последнего столбца становятся одинаковыми или мы попадаем в первый столбец.

    while (column[min_row] >= 0) {

        // Находим минимум в текущем последнем столбце

        for (i = 0; i < M; i++) {

            if (mat[i][column[i]] < mat[min_row][column[min_row]])

                min_row = i;

        }

  

        // eq_count - количество элементов, равное минимуму в текущем последнем

        // столбец.

        int eq_count = 0;

  

        // Переходим к текущему последнему элементу столбца, чтобы обновить его

        for (i = 0; i < M; i++) {

            // Уменьшаем индекс последнего столбца строки, значение которой больше

            // чем минимум.

            if (mat[i][column[i]] > mat[min_row][column[min_row]]) {

                if (column[i] == 0)

                    return -1;

  

                column[i] -= 1; // Уменьшаем индекс последнего столбца на 1

            }

            else

                eq_count++;

        }

  

        // Если равный счет становится М, вернуть значение

        if (eq_count == M)

            return mat[min_row][column[min_row]];

    }

    return -1;

}

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

int main()

{

    int mat[M][N] = {

        { 1, 2, 3, 4, 5 },

        { 2, 4, 5, 8, 10 },

        { 3, 5, 7, 9, 11 },

        { 1, 3, 5, 7, 9 },

    };

    int result = findCommon(mat);

    if (result == -1)

        cout << "No common element";

    else

        cout << "Common element is " << result;

    return 0;

}

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

С

// Программа AC для поиска общего элемента во всех строках
// отсортированный по ряду массив
#include <stdio.h>

  
// Укажите количество строк и столбцов
#define M 4
#define N 5

  
// Возвращает общий элемент во всех строках mat [M] [N]. Если нет
// общий элемент, затем возвращается -1

int findCommon(int mat[M][N])

{

    // Массив для хранения индексов текущего последнего столбца

    int column[M];

    int min_row; // Хранить индекс строки, текущий

    // последний элемент минимальный

  

    // Инициализируем текущий последний элемент всех строк

    int i;

    for (i = 0; i < M; i++)

        column[i] = N - 1;

  

    min_row = 0; // Инициализируем min_row как первый ряд

  

    // Продолжаем находить min_row в текущем последнем столбце, пока либо

    // все элементы последнего столбца становятся одинаковыми или мы попадаем в первый столбец.

    while (column[min_row] >= 0) {

        // Находим минимум в текущем последнем столбце

        for (i = 0; i < M; i++) {

            if (mat[i][column[i]] < mat[min_row][column[min_row]])

                min_row = i;

        }

  

        // eq_count - количество элементов, равное минимуму в текущем последнем

        // столбец.

        int eq_count = 0;

  

        // Переходим к текущему последнему элементу столбца, чтобы обновить его

        for (i = 0; i < M; i++) {

            // Уменьшаем индекс последнего столбца строки, значение которой больше

            // чем минимум.

            if (mat[i][column[i]] > mat[min_row][column[min_row]]) {

                if (column[i] == 0)

                    return -1;

  

                column[i] -= 1; // Уменьшаем индекс последнего столбца на 1

            }

            else

                eq_count++;

        }

  

        // Если равный счет становится М, вернуть значение

        if (eq_count == M)

            return mat[min_row][column[min_row]];

    }

    return -1;

}

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

int main()

{

    int mat[M][N] = {

        { 1, 2, 3, 4, 5 },

        { 2, 4, 5, 8, 10 },

        { 3, 5, 7, 9, 11 },

        { 1, 3, 5, 7, 9 },

    };

    int result = findCommon(mat);

    if (result == -1)

        printf("No common element");

    else

        printf("Common element is %d", result);

    return 0;

}

Джава

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

  

class GFG {

    // Укажите количество строк и столбцов

    static final int M = 4;

    static final int N = 5;

  

    // Возвращает общий элемент во всех строках

    // мата [M] [N]. Если нет

    // общий элемент, то -1

    // вернулся

    static int findCommon(int mat[][])

    {

        // Массив для хранения индексов

        // текущего последнего столбца

        int column[] = new int[M];

  

        // Хранить индекс строки, текущий

        // последний элемент минимальный

        int min_row;

  

        // Инициализируем текущий последний элемент всех строк

        int i;

        for (i = 0; i < M; i++)

            column[i] = N - 1;

  

        // Инициализируем min_row как первый ряд

        min_row = 0;

  

        // Продолжаем находить min_row в текущем последнем столбце, пока либо

        // все элементы последнего столбца становятся одинаковыми или мы попадаем в первый столбец.

        while (column[min_row] >= 0) {

            // Находим минимум в текущем последнем столбце

            for (i = 0; i < M; i++) {

                if (mat[i][column[i]] < mat[min_row][column[min_row]])

                    min_row = i;

            }

  

            // eq_count - количество элементов, равное минимуму в текущем последнем

            // столбец.

            int eq_count = 0;

  

            // Переходим к текущему последнему элементу столбца, чтобы обновить его

            for (i = 0; i < M; i++) {

                // Уменьшаем индекс последнего столбца строки, значение которой больше

                // чем минимум.

                if (mat[i][column[i]] > mat[min_row][column[min_row]]) {

                    if (column[i] == 0)

                        return -1;

  

                    // Уменьшаем индекс последнего столбца на 1

                    column[i] -= 1;

                }

                else

                    eq_count++;

            }

  

            // Если равный счет становится М,

            // вернуть значение

            if (eq_count == M)

                return mat[min_row][column[min_row]];

        }

        return -1;

    }

  

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

    public static void main(String[] args)

    {

        int mat[][] = { { 1, 2, 3, 4, 5 },

                        { 2, 4, 5, 8, 10 },

                        { 3, 5, 7, 9, 11 },

                        { 1, 3, 5, 7, 9 } };

        int result = findCommon(mat);

        if (result == -1)

            System.out.print("No common element");

        else

            System.out.print("Common element is " + result);

    }

}

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

Python 3

# Python 3 программа для поиска общего элемента
# во всех строках строки отсортированный массив

  
# Укажите количество строк
# и столбцы

M = 4

N = 5

  
# Возвращает общий элемент во всех строках
№ мата [M] [N]. Если нет общего
# элемент, тогда возвращается -1

def findCommon(mat):

  

    # Массив для хранения индексов

    # текущий последний столбец

    column = [N - 1] * M

  

    min_row = 0 # Инициализировать min_row как первый ряд

  

    # Продолжайте находить min_row в текущем последнем

    # столбец, пока либо все элементы

    # последний столбец становится таким же или мы попадаем в первый столбец.

    while (column[min_row] >= 0):

      

        # Найти минимум в текущем последнем столбце

        for i in range(M):

            if (mat[i][column[i]] < 

                mat[min_row][column[min_row]]):

                min_row = i

      

        # eq_count - количество элементов, равное

        # до минимума в текущем последнем столбце.

        eq_count = 0

  

        # Обход текущего элемента последнего столбца

        # еще раз, чтобы обновить его

        for i in range(M):

              

            # Уменьшить индекс последней колонки строки

            # значение которого больше минимального.

            if (mat[i][column[i]] > 

                mat[min_row][column[min_row]]):

                if (column[i] == 0):

                    return -1

  

                column[i] -= 1 # Уменьшить последний столбец

                               # индекс по 1

          

            else:

                eq_count += 1

  

        # Если равный счет становится М, вернуть значение

        if (eq_count == M):

            return mat[min_row][column[min_row]]

    return -1

  
Код водителя

if __name__ == "__main__":

      

    mat = [[1, 2, 3, 4, 5],

           [2, 4, 5, 8, 10],

           [3, 5, 7, 9, 11],

           [1, 3, 5, 7, 9]]

  

    result = findCommon(mat)

    if (result == -1):

        print("No common element")

    else:

        print("Common element is", result)

  
# Этот код предоставлен ita_c

C #

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

using System;

  

class GFG {

  

    // Укажите количество строк и столбцов

    static int M = 4;

    static int N = 5;

  

    // Возвращает общий элемент во всех строках

    // мата [M] [N]. Если нет

    // общий элемент, то -1

    // вернулся

    static int findCommon(int[, ] mat)

    {

  

        // Массив для хранения индексов

        // текущего последнего столбца

        int[] column = new int[M];

  

        // Хранить индекс строки, чьи

        // текущий последний элемент минимален

        int min_row;

  

        // Инициализируем текущий последний элемент

        // всех строк

        int i;

        for (i = 0; i < M; i++)

            column[i] = N - 1;

  

        // Инициализируем min_row как первый ряд

        min_row = 0;

  

        // Продолжаем находить min_row в текущем

        // последний столбец, пока либо все

        // элементы последнего столбца становятся

        // то же самое или мы попали в первый столбец.

        while (column[min_row] >= 0) {

  

            // Находим минимум в текущем

            // последний столбец

            for (i = 0; i < M; i++) {

                if (mat[i, column[i]] < mat[min_row, column[min_row]])

                    min_row = i;

            }

  

            // eq_count - количество элементов

            // равен минимуму в текущем

            // последний столбец.

            int eq_count = 0;

  

            // Обход текущего последнего столбца

            // элементы снова, чтобы обновить его

            for (i = 0; i < M; i++) {

  

                // Уменьшаем индекс последнего столбца

                // строки, значение которой больше

                // чем минимум.

                if (mat[i, column[i]] > mat[min_row, column[min_row]]) {

                    if (column[i] == 0)

                        return -1;

  

                    // Уменьшаем индекс последнего столбца

                    // на 1

                    column[i] -= 1;

                }

                else

                    eq_count++;

            }

  

            // Если равный счет становится М,

            // вернуть значение

            if (eq_count == M)

                return mat[min_row,

                           column[min_row]];

        }

  

        return -1;

    }

  

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

    public static void Main()

    {

        int[, ] mat = { { 1, 2, 3, 4, 5 },

                        { 2, 4, 5, 8, 10 },

                        { 3, 5, 7, 9, 11 },

                        { 1, 3, 5, 7, 9 } };

  

        int result = findCommon(mat);

  

        if (result == -1)

            Console.Write("No common element");

        else

            Console.Write("Common element is "

                          + result);

    }

}

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

Выход:

Common element is 5

Выход:

Common element is 5

Объяснение для работы вышеуказанного кода
Давайте разберемся в работе вышеприведенного кода для следующего примера.

Первоначально записи в последнем массиве столбцов — N-1, то есть {4, 4, 4, 4}
{1, 2, 3, 4, 5 },
{2, 4, 5, 8, 10 },
{3, 5, 7, 9, 11 },
{1, 3, 5, 7, 9 },

Значение min_row равно 0, поэтому значения индекса последнего столбца для строк со значением больше 5 уменьшаются на единицу. Таким образом, столбец [] становится {4, 3, 3, 3}.
{1, 2, 3, 4, 5 },
{2, 4, 5, 8 , 10},
{3, 5, 7, 9 , 11},
{1, 3, 5, 7 , 9},

Значение min_row остается 0, а значение индекса последнего столбца для строк со значением больше 5 уменьшается на единицу. Таким образом, столбец [] становится {4, 2, 2, 2}.
{1, 2, 3, 4, 5 },
{2, 4, 5 , 8, 10},
{3, 5, 7 , 9, 11},
{1, 3, 5 , 7, 9},

Значение min_row остается 0, а значение индекса последнего столбца для строк со значением больше 5 уменьшается на единицу. Таким образом, colomun [] становится {4, 2, 1, 2}.
{1, 2, 3, 4, 5 },
{2, 4, 5 , 8, 10},
{3, 5 , 7, 9, 11},
{1, 3, 5 , 7, 9},

Теперь все значения в текущих последних столбцах всех строк одинаковы, поэтому возвращается 5.

Решение на основе хеширования
Мы также можем использовать хеширование. Это решение работает, даже если строки не отсортированы. Он может быть использован для печати всех общих элементов.

Step1:  Create a Hash Table with all key as distinct elements 
        of row1. Value for all these will be 0.

Step2:  
For i = 1 to M-1
 For j = 0 to N-1
  If (mat[i][j] is already present in Hash Table)
   If (And this is not a repetition in current row.
      This can be checked by comparing HashTable value with
      row number)
         Update the value of this key in HashTable with current 
         row number

Step3: Iterate over HashTable and print all those keys for 
       which value = M 

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Укажите количество строк и столбцов
#define M 4
#define N 5

  
// Возвращает общий элемент во всех строках mat [M] [N]. Если нет
// общий элемент, затем возвращается -1

int findCommon(int mat[M][N])

{

    // Хеш-карта для хранения количества элементов

    unordered_map<int, int> cnt;

  

    int i, j;

  

    for (i = 0; i < M; i++) {

  

        // Увеличиваем количество первых

        // элемент строки

        cnt[mat[i][0]]++;

  

        // Начиная со второго элемента

        // текущей строки

        for (j = 1; j < N; j++) {

  

            // Если текущий элемент отличается от

            // предыдущий элемент т.е. он появляется

            // впервые в текущей строке

            if (mat[i][j] != mat[i][j - 1])

                cnt[mat[i][j]]++;

        }

    }

  

    // Найти элемент с количеством строк равным количеству строк

    for (auto ele : cnt) {

        if (ele.second == M)

            return ele.first;

    }

  

    // Такой элемент не найден

    return -1;

}

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

int main()

{

    int mat[M][N] = {

        { 1, 2, 3, 4, 5 },

        { 2, 4, 5, 8, 10 },

        { 3, 5, 7, 9, 11 },

        { 1, 3, 5, 7, 9 },

    };

    int result = findCommon(mat);

    if (result == -1)

        cout << "No common element";

    else

        cout << "Common element is " << result;

  

    return 0;

}

Джава

// Java реализация подхода

import java.util.*;

  

class GFG 

{

  
// Укажите количество строк и столбцов

static int M = 4;

static int N = 5;

  
// Возвращает общий элемент во всех строках mat [M] [N].
// Если общего элемента нет, то возвращается -1

static int findCommon(int mat[][])

{

    // Хеш-карта для хранения количества элементов

    HashMap<Integer, 

            Integer> cnt = new HashMap<Integer, 

                                       Integer>();

  

    int i, j;

  

    for (i = 0; i < M; i++) 

    {

  

        // Увеличиваем количество первых

        // элемент строки

        if(cnt.containsKey(mat[i][0]))

        {

            cnt.put(mat[i][0], 

            cnt.get(mat[i][0]) + 1);

        }

        else

        {

            cnt.put(mat[i][0], 1);

        }

  

        // Начиная со второго элемента

        // текущей строки

        for (j = 1; j < N; j++) 

        {

  

            // Если текущий элемент отличается от

            // предыдущий элемент т.е. он появляется

            // впервые в текущей строке

            if (mat[i][j] != mat[i][j - 1])

                if(cnt.containsKey(mat[i][j]))

                {

                    cnt.put(mat[i][j], 

                    cnt.get(mat[i][j]) + 1);

                }

                else

                {

                    cnt.put(mat[i][j], 1);

                }

        }

    }

  

    // Найти элемент с количеством

    // равно количеству строк

    for (Map.Entry<Integer, 

                   Integer> ele : cnt.entrySet())

    {

        if (ele.getValue() == M)

            return ele.getKey();

    }

  

    // Такой элемент не найден

    return -1;

}

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

public static void main(String[] args) 

{

    int mat[][] = {{ 1, 2, 3, 4, 5 },

                   { 2, 4, 5, 8, 10 },

                   { 3, 5, 7, 9, 11 },

                   { 1, 3, 5, 7, 9 }};

    int result = findCommon(mat);

    if (result == -1)

        System.out.println("No common element");

    else

        System.out.println("Common element is " + result);

    }

}

  
// Этот код предоставлен Rajput-Ji

C #

// C # реализация подхода

using System;

using System.Collections.Generic; 

  

class GFG 

{

  
// Укажите количество строк и столбцов

static int M = 4;

static int N = 5;

  
// Возвращает общий элемент во всех строках mat [M, N].
// Если общего элемента нет, то возвращается -1

static int findCommon(int [,]mat)

{

    // Хеш-карта для хранения количества элементов

    Dictionary<int,

               int> cnt = new Dictionary<int

                                         int>();

  

    int i, j;

  

    for (i = 0; i < M; i++) 

    {

  

        // Увеличиваем количество первых

        // элемент строки

        if(cnt.ContainsKey(mat[i, 0]))

        {

            cnt[mat[i, 0]]= cnt[mat[i, 0]] + 1;

        }

        else

        {

            cnt.Add(mat[i, 0], 1);

        }

  

        // Начиная со второго элемента

        // текущей строки

        for (j = 1; j < N; j++) 

        {

  

            // Если текущий элемент отличается от

            // предыдущий элемент т.е. он появляется

            // впервые в текущей строке

            if (mat[i, j] != mat[i, j - 1])

                if(cnt.ContainsKey(mat[i, j]))

                {

                    cnt[mat[i, j]]= cnt[mat[i, j]] + 1;

                }

                else

                {

                    cnt.Add(mat[i, j], 1);

                }

        }

    }

  

    // Найти элемент с количеством

    // равно количеству строк

    foreach(KeyValuePair<int, int> ele in cnt)

    {

        if (ele.Value == M)

            return ele.Key;

    }

  

    // Такой элемент не найден

    return -1;

}

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

public static void Main(String[] args) 

{

    int [,]mat = {{ 1, 2, 3, 4, 5 },

                  { 2, 4, 5, 8, 10 },

                  { 3, 5, 7, 9, 11 },

                  { 1, 3, 5, 7, 9 }};

    int result = findCommon(mat);

    if (result == -1)

        Console.WriteLine("No common element");

    else

        Console.WriteLine("Common element is " + result);

    }

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

Выход:

Common element is 5

Временная сложность вышеупомянутого решения на основе хеширования составляет O (MN) в предположении, что поиск и вставка в HashTable занимают O (1) время. Спасибо Nishant за предложенное решение в комментарии ниже.

Упражнение: Учитывая n отсортированных массивов размером m каждый, найдите все общие элементы во всех массивах за O (mn) времени.

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

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

Найти общий элемент во всех строках данной отсортированной по строке матрицы

0.00 (0%) 0 votes