Рубрики

Вывести все элементы в отсортированном порядке из отсортированной по строке и столбцу матрицы

Heap, Матрицы

Дана матрица nxn, где каждая строка и столбец отсортированы в неубывающем порядке. Распечатать все элементы матрицы в отсортированном порядке.

Пример:

Input: mat[][]  =  { {10, 20, 30, 40},
                     {15, 25, 35, 45},
                     {27, 29, 37, 48},
                     {32, 33, 39, 50},
                   };

Output:
Elements of matrix in sorted order
10 15 20 25 27 29 30 32 33 35 37 39 40 45 48 50

Мы можем использовать Young Tableau для решения вышеуказанной проблемы. Идея состоит в том, чтобы рассматривать данный двумерный массив как таблицу Юнга и вызывать минимум извлечения O (N)

C ++

// Программа на C ++ для печати всех элементов в отсортированном порядке из строки и
// отсортированная по столбцам матрица
#include<iostream>
#include<climits>

using namespace std;

  
#define INF INT_MAX
#define N 4

  
// Вспомогательная функция для создания молодой таблицы. Это разные
// из стандартного младшего. Предполагается, что значение в mat [0] [0] равно
// бесконечно.

void youngify(int mat[][N], int i, int j)

{

    // Находим значения внизу и справа от mat [i] [j]

    int downVal  = (i+1 < N)? mat[i+1][j]: INF;

    int rightVal = (j+1 < N)? mat[i][j+1]: INF;

  

    // Если mat [i] [j] - нижний правый угловой элемент, возвращаем

    if (downVal==INF && rightVal==INF)

        return;

  

    // Переместить меньшее из двух значений (downVal и rightVal) в

    // mat [i] [j] и повторение для меньшего значения

    if (downVal < rightVal)

    {

        mat[i][j] = downVal;

        mat[i+1][j] = INF;

        youngify(mat, i+1, j);

    }

    else

    {

        mat[i][j] = rightVal;

        mat[i][j+1] = INF;

        youngify(mat, i, j+1);

    }

}

  
// Полезная функция для извлечения минимального элемента из таблицы Юнга

int extractMin(int mat[][N])

{

    int ret = mat[0][0];

    mat[0][0] = INF;

    youngify(mat, 0, 0);

    return ret;

}

  
// Эта функция использует extractMin () для печати элементов в отсортированном порядке

void printSorted(int mat[][N])

{

   cout << "Elements of matrix in sorted order n";

   for (int i=0; i<N*N; i++)

     cout << extractMin(mat) << " ";

}

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

int main()

{

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

                    {15, 25, 35, 45},

                    {27, 29, 37, 48},

                    {32, 33, 39, 50},

                  };

  printSorted(mat);

  return 0;

}

Джава

// Java-программа для печати всех элементов
// в отсортированном порядке от строки и
// отсортированная по столбцам матрица

class GFG 

{

    static final int INF = Integer.MAX_VALUE;

    static final int N = 4;

  

    // Вспомогательная функция для создания молодой таблицы.

    // Это отличается от стандартного youngify.

    // Предполагается, что значение в mat [0] [0] бесконечно.

    static void youngify(int mat[][], int i, int j)

    {

        // Находим значения внизу и справа от mat [i] [j]

        int downVal = (i + 1 < N) ? 

                    mat[i + 1][j] : INF;

        int rightVal = (j + 1 < N) ? 

                     mat[i][j + 1] : INF;

  

        // Если mat [i] [j] - нижний правый угловой элемент,

        // возвращение

        if (downVal == INF && rightVal == INF) 

        {

            return;

        }

  

        // Переместить меньшее из двух значений

        // (downVal и rightVal) для mat [i] [j]

        // и повторить для меньшего значения

        if (downVal < rightVal)

        {

            mat[i][j] = downVal;

            mat[i + 1][j] = INF;

            youngify(mat, i + 1, j);

        } 

        else 

        {

            mat[i][j] = rightVal;

            mat[i][j + 1] = INF;

            youngify(mat, i, j + 1);

        }

    }

  

    // Утилита для извлечения

    // минимальный элемент из таблицы Юнга

    static int extractMin(int mat[][]) 

    {

        int ret = mat[0][0];

        mat[0][0] = INF;

        youngify(mat, 0, 0);

        return ret;

    }

  

    // Эта функция использует extractMin ()

    // для печати элементов в отсортированном порядке

    static void printSorted(int mat[][]) 

    {

        System.out.println("Elements of matrix in sorted order n");

        for (int i = 0; i < N * N; i++) 

        {

            System.out.print(extractMin(mat) + " ");

        }

    }

  

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

    public static void main(String args[]) 

    {

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

                       {15, 25, 35, 45},

                       {27, 29, 37, 48},

                       {32, 33, 39, 50}};

        printSorted(mat);

    }

}

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

Python 3

# Программа Python 3 для печати всех элементов
# в отсортированном порядке из строки и столбца
# разумно отсортированная матрица

import sys

  

INF = sys.maxsize

N = 4

  
# Функция полезности для молодости
# Таблица. Это отличается от стандартного
# youngify. Предполагается, что значение в
# mat [0] [0] бесконечно.

def youngify(mat, i, j):

  

    # Найти значения вниз и

    # правые стороны мата [i] [j]

    downVal = mat[i + 1][j] if (i + 1 < N) else INF

    rightVal = mat[i][j + 1] if (j + 1 < N) else INF

  

    # Если mat [i] [j] внизу справа

    # угловой элемент, возврат

    if (downVal == INF and rightVal == INF):

        return

  

    # Переместить меньшее из двух значений

    # (downVal и rightVal) в mat [i] [j]

    # и повторить для меньшего значения

    if (downVal < rightVal):

        mat[i][j] = downVal

        mat[i + 1][j] = INF

        youngify(mat, i + 1, j)

      

    else:

        mat[i][j] = rightVal

        mat[i][j + 1] = INF

        youngify(mat, i, j + 1)

  
# Полезная функция для извлечения минимума
# элемент из молодой таблицы

def extractMin(mat):

  

    ret = mat[0][0]

    mat[0][0] = INF

    youngify(mat, 0, 0)

    return ret

  
# Эта функция использует extractMin () для
# печать элементов в отсортированном порядке

def printSorted(mat):

          

    print("Elements of matrix in sorted order n")

    i = 0

    while i < N * N: 

        print(extractMin(mat), end = " ")

        i += 1

  
Код водителя

if __name__ == "__main__":

      

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

           [15, 25, 35, 45],

           [27, 29, 37, 48],

           [32, 33, 39, 50]]

    printSorted(mat)

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

C #

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

using System;

  

class GFG

{

    static int INF = int.MaxValue;

    static int N = 4;

  

    // Вспомогательная функция для создания молодой таблицы.

    // Это отличается от стандартного youngify.

    // Предполагается, что значение в mat [0] [0] бесконечно.

    static void youngify(int [,]mat, int i, int j)

    {

        // Находим значения внизу и справа от mat [i] [j]

        int downVal = (i + 1 < N) ? 

                    mat[i + 1,j] : INF;

        int rightVal = (j + 1 < N) ? 

                    mat[i,j + 1] : INF;

  

        // Если mat [i] [j] - нижний правый угловой элемент,

        // возвращение

        if (downVal == INF && rightVal == INF) 

        {

            return;

        }

  

        // Переместить меньшее из двух значений

        // (downVal и rightVal) для mat [i] [j]

        // и повторить для меньшего значения

        if (downVal < rightVal)

        {

            mat[i,j] = downVal;

            mat[i + 1,j] = INF;

            youngify(mat, i + 1, j);

        } 

        else

        {

            mat[i, j] = rightVal;

            mat[i, j + 1] = INF;

            youngify(mat, i, j + 1);

        }

    }

  

    // Утилита для извлечения

    // минимальный элемент из таблицы Юнга

    static int extractMin(int [,]mat) 

    {

        int ret = mat[0,0];

        mat[0, 0] = INF;

        youngify(mat, 0, 0);

        return ret;

    }

  

    // Эта функция использует extractMin ()

    // для печати элементов в отсортированном порядке

    static void printSorted(int [,]mat) 

    {

            Console.WriteLine("Elements of matrix in sorted order n");

        for (int i = 0; i < N * N; i++) 

        {

            Console.Write(extractMin(mat) + " ");

        }

    }

  

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

    static public void Main ()

    {

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

                    {15, 25, 35, 45},

                    {27, 29, 37, 48},

                    {32, 33, 39, 50}};

        printSorted(mat);

    }

}

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


Выход:

Elements of matrix in sorted order
10 15 20 25 27 29 30 32 33 35 37 39 40 45 48 50

Временная сложность извлечения минимума составляет O (N) и называется O (N 2 ) раз. Следовательно, общая временная сложность составляет O (N 3 ).

Лучшим решением является использование подхода, используемого для объединения k отсортированных массивов . Идея состоит в том, чтобы использовать Min Heap размера N, в которой хранятся элементы первого столбца. До извлечения минимум. В минимуме извлечения замените минимальный элемент следующим элементом строки, из которой извлечен элемент. Временная сложность этого решения составляет O (N 2 LogN).

   
// C ++ программа для объединения k отсортированных массивов размером n каждый.
#include<iostream>
#include<climits>

using namespace std;

  
#define N 4

  
// Узел минимальной кучи

struct MinHeapNode

{

    int element; // Элемент, который будет сохранен

    int i; // индекс строки, из которой взят элемент

    int j; // индекс следующего элемента, который будет выбран из строки

};

  
// Прототип служебной функции для замены двух минимальных узлов кучи

void swap(MinHeapNode *x, MinHeapNode *y);

  
// Класс для Min Heap

class MinHeap

{

    MinHeapNode *harr; // указатель на массив элементов в куче

    int heap_size; // размер кучи мин

public:

    // Конструктор: создает минимальную кучу заданного размера

    MinHeap(MinHeapNode a[], int size);

  

    // сложить поддерево с корнем по заданному индексу

    void MinHeapify(int );

  

    // получить индекс левого потомка узла по индексу i

    int left(int i) { return (2*i + 1); }

  

    // получить индекс правого потомка узла по индексу i

    int right(int i) { return (2*i + 2); }

  

    // чтобы получить рут

    MinHeapNode getMin() { return harr[0]; }

  

    // заменить корень новым узлом x и heapify () новым корнем

    void replaceMin(MinHeapNode x) { harr[0] = x;  MinHeapify(0); }

};

  
// Эта функция печатает элементы данной матрицы в неубывающем
// заказ. Предполагается, что ma [] [] отсортировано по строке.

void printSorted(int mat[][N])

{

    // Создать минимальную кучу с k узлами кучи. Каждый узел кучи

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

    MinHeapNode *harr = new MinHeapNode[N];

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

    {

        harr[i].element = mat[i][0]; // Сохраняем первый элемент

        harr[i].i = i;  // индекс строки

        harr[i].j = 1;  // Индекс следующего элемента, который будет сохранен из строки

    }

    MinHeap hp(harr, N); // Создаем минимальную кучу

  

    // Теперь один за другим получаем минимальный элемент из min

    // куча и заменить его следующим элементом массива

    for (int count = 0; count < N*N; count++)

    {

        // Получить минимальный элемент и сохранить его на выходе

        MinHeapNode root = hp.getMin();

  

        cout << root.element << " ";

  

        // Найти следующий элемент, который заменит текущий

        // корень кучи. Следующий элемент принадлежит тому же

        // массив в качестве текущего корня.

        if (root.j < N)

        {

            root.element = mat[root.i][root.j];

            root.j += 1;

        }

        // Если корень был последним элементом своего массива

        else root.element =  INT_MAX; // INT_MAX для бесконечного

  

        // Заменить корень на следующий элемент массива

        hp.replaceMin(root);

    }

}

  
// СЛЕДУЮЩИЕ РЕАЛИЗАЦИИ СТАНДАРТНЫХ МЕТОДОВ MIN MIN HEAP
// ИЗ КОРМЕНСКОЙ КНИГИ
// Конструктор: строит кучу из заданного массива a [] заданного размера

MinHeap::MinHeap(MinHeapNode a[], int size)

{

    heap_size = size;

    harr = a;  // сохранить адрес массива

    int i = (heap_size - 1)/2;

    while (i >= 0)

    {

        MinHeapify(i);

        i--;

    }

}

  
// Рекурсивный метод, чтобы накапливать поддерево с корнем по заданному индексу
// Этот метод предполагает, что поддеревья уже сложены

void MinHeap::MinHeapify(int i)

{

    int l = left(i);

    int r = right(i);

    int smallest = i;

    if (l < heap_size && harr[l].element < harr[i].element)

        smallest = l;

    if (r < heap_size && harr[r].element < harr[smallest].element)

        smallest = r;

    if (smallest != i)

    {

        swap(&harr[i], &harr[smallest]);

        MinHeapify(smallest);

    }

}

  
// Утилита для замены двух элементов

void swap(MinHeapNode *x, MinHeapNode *y)

{

    MinHeapNode temp = *x;  *x = *y;  *y = temp;

}

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

int main()

{

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

                    {15, 25, 35, 45},

                    {27, 29, 37, 48},

                    {32, 33, 39, 50},

                  };

  printSorted(mat);

  return 0;

}

Выход:

10 15 20 25 27 29 30 32 33 35 37 39 40 45 48 50

Упражнение:
Вышеуказанные решения работают для квадратной матрицы. Расширьте вышеприведенные решения для работы с прямоугольной матрицей M * N.

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

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

Вывести все элементы в отсортированном порядке из отсортированной по строке и столбцу матрицы

0.00 (0%) 0 votes