Рубрики

Распечатать nxn спиральную матрицу, используя O (1) дополнительное пространство

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

Input: n = 5
Output:
25 24 23 22 21
10  9  8  7 20
11  2  1  6 19
12  3  4  5 18
13 14 15 16 17

Мы настоятельно рекомендуем вам свернуть браузер и попробовать это в первую очередь.

Решение становится простым, если разрешено дополнительное пространство. Мы выделяем память для матрицы nxn и для каждого элемента, начиная с n * n до 1, начинаем заполнять матрицу в спиральном порядке. Для поддержания порядка спирали используются четыре цикла, каждый для верхнего, правого, нижнего и левого угла матрицы.

Но как решить это в O (1) пространстве?

Матрица nxn имеет квадраты циклов (n / 2). Цикл состоит из i-й строки, (n-i + 1) -го столбца, (n-i + 1) -й строки и i-го столбца, где i изменяется от 1 до ceil (n / 2).

25 24 23 22 21 
10 9  8  7  20
11 2  1  6  19
12 3  4  5  18
13 14 15 16 17
  1. Первый цикл состоит из элементов его первого ряда, последнего столбца, последнего ряда и первого столбца (отмечены красным ). Первый цикл состоит из элементов от n * n до (n-2) * (n-2) + 1, т.е. от 25 до 10.
  2. Второй цикл состоит из элементов второго ряда, второго-последнего столбца, второго-последнего ряда и второго столбца (отмечены синим цветом ). Второй цикл состоит из элементов от (n-2) * (n-2) до (n-4) * (n-4) + 1, т.е. от 9 до 2.
  3. Третий цикл состоит из элементов третьего ряда, третьего-последнего столбца, третьего-последнего ряда и третьего столбца (отмечены черным ). Третий цикл состоит из элементов от (n-4) * (n-4) до 1. т.е. только 1.

Идея для каждого квадратного цикла, мы привязываем к нему маркер. Для внешнего цикла маркер будет иметь значение 0, для второго цикла он будет иметь значение 1, а для третьего цикла — значение 2. Как правило, для матрицы тревожных сигналов i-й цикл будет иметь значение маркера i — 1.

Если мы разделим матрицу на две части, верхний правый треугольник (отмечен оранжевым цветом ) и нижний левый треугольник (отмечен зеленым цветом ), то с помощью маркера x мы можем легко вычислить значение, которое будет присутствовать в индексе (i, j ) в любой nxn спиральной матрице, используя следующую формулу —

25  24 23 22 21 
10  9  8  7  20 
11  2  1  6  19 
12  3  4  5  18 
13  14 15 16 17 
For upper right half,
mat[i][j] = (n-2*x)*(n-2*x)-(i-x)-(j-x)

For lower left half,
mat[i][j] = (n-2*x-2)*(n-2*x-2) + (i-x) + (j-x)

Ниже приведена реализация идеи.

C ++

// C ++ программа для печати тревожной спиральной матрицы
// по часовой стрелке, используя пробел O (1)
#include <bits/stdc++.h>

using namespace std;

  
// Печатает спиральную матрицу размером nxn, содержащую
// числа от 1 до nxn

void printSpiral(int n)

{

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

    {

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

        {

            // x хранит слой, в котором (i, j) th

            // элемент лжи

            int x;

  

            // Находит минимум четыре входа

            x = min(min(i, j), min(n-1-i, n-1-j));

  

            // Для верхней правой половины

            if (i <= j)

                printf("%d\t ", (n-2*x)*(n-2*x) - (i-x)

                    - (j-x));

  

            // для нижней левой половины

            else

                printf("%d\t ", (n-2*x-2)*(n-2*x-2) + (i-x)

                    + (j-x));

        }

        printf("\n");

    }

}

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

int main()

{

    int n = 5;

  

    // выводим спиральную матрицу тревог в пространстве O (1)

    printSpiral(n);

  

    return 0;

}

Джава

// Java-программа для печати тревожной спиральной матрицы
// по часовой стрелке, используя пробел O (1)

  

import java.io.*;

import java.util.*;

  

class GFG {

  

    // Печатает спиральную матрицу размером nxn

    // содержит числа от 1 до nxn

    static void printSpiral(int n)

    {

        for (int i = 0; i < n; i++) {

            for (int j = 0; j < n; j++) {

                  

                // x хранит слой, в котором (i, j) th

                // элемент лжи

                int x;

  

                // Находит минимум четыре входа

                x = Math.min(Math.min(i, j), 

                    Math.min(n - 1 - i, n - 1 - j));

  

                // Для верхней правой половины

                if (i <= j)

                    System.out.print((n - 2 * x) * (n - 2 * x) - 

                                     (i - x) - (j - x) + "\t");

  

                // для нижней левой половины

                else

                    System.out.print((n - 2 * x - 2) * (n - 2 * x - 2) +

                                     (i - x) + (j - x) + "\t");

            }

            System.out.println();

        }

    }

  

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

    public static void main(String args[])

    {

        int n = 5;

  

        // выводим спиральную матрицу тревог в пространстве O (1)

        printSpiral(n);

    }

}

  
/ * Этот код предоставлен Никитой Тивари. * /

python3

# Python3 программа для печати тревожной спиральной матрицы
# по часовой стрелке, используя пробел O (1)

  
# Печатает спиральную матрицу размером nxn
# содержит числа от 1 до nxn

def printSpiral(n) :

      

    for i in range(0, n) :

        for j in range(0, n) :

              

            # Находит минимум четыре входа

            x = min(min(i, j), min(n - 1 - i, n - 1 - j))

              

            # Для верхней правой половины

            if (i <= j) :

                print((n - 2 * x) * (n - 2 * x) -

                      (i - x)- (j - x), end = "\t")

  

            # Для нижней левой половины

            else :

                print(((n - 2 * x - 2) *

                       (n - 2 * x - 2) +

                       (i - x) + (j - x)), end = "\t")

        print()

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

n = 5

  
# печать тревожной спиральной матрицы
# в O (1) пространстве
printSpiral(n)

  
# Этот код предоставлен Никитой Тивари.

C #

// C # программа для печати проблем
// спиральная матрица по часовой стрелке
// направление с использованием пробела O (1)

using System;

  

class GFG {

  

    // Печатает спиральную матрицу

    // размер nxn содержащий

    // числа от 1 до nxn

    static void printSpiral(int n)

    {

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

        {

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

            {

                  

                // х хранит слой, в котором

                // (i, j) -ый элемент лежит

                int x;

  

                // Находит минимум четыре входа

                x = Math.Min(Math.Min(i, j), 

                    Math.Min(n - 1 - i, n - 1 - j));

  

                // Для верхней правой половины

                if (i <= j)

                    Console.Write((n - 2 * x) * 

                                  (n - 2 * x) - 

                                  (i - x) - (j - x) + "\t");

  

                // для нижней левой половины

                else

                    Console.Write((n - 2 * x - 2) * 

                                  (n - 2 * x - 2) + 

                                  (i - x) + (j - x) + "\t");

            }

            Console.WriteLine();

        }

    }

  

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

    public static void Main()

    {

        int n = 5;

  

        // распечатать спираль тревоги

        // матрица в пространстве O (1)

        printSpiral(n);

    }

}

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

PHP

<?php
// PHP программа для печати тревог
// спиральная матрица по часовой стрелке
// направление с использованием пробела O (1)

  
// Печатает спиральную матрицу размера
// nxn, содержащий числа
// от 1 до nxn

function printSpiral($n)

{

    for ($i = 0; $i < $n; $i++)

    {

        for ($j = 0; $j < $n; $j++)

        {

            // х сохраняет слой в

            // какой (i, j) -й элемент лежит

            $x;

  

            // Находит минимум четыре входа

            $x = min(min($i, $j), min($n - 1 - $i

                                      $n - 1 - $j));

  

            // Для верхней правой половины

            if ($i <= $j)

                echo "\t ", ($n - 2 * $x) * 

                            ($n - 2 * $x) - 

                            ($i - $x) - ($j - $x);

  

            // для нижней левой половины

            else

                echo "\t ", ($n - 2 * $x - 2) * 

                            ($n - 2 * $x - 2) + 

                            ($i - $x) + ($j - $x);

        }

        echo "\n";

    }

}

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

$n = 5;

  
// распечатать спираль тревоги
// матрица в пространстве O (1)

printSpiral($n);

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


Выход :

25     24     23     22     21     
10     9     8     7     20     
11     2     1     6     19     
12     3     4     5     18     
13     14     15     16     17

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

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

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

Распечатать nxn спиральную матрицу, используя O (1) дополнительное пространство

0.00 (0%) 0 votes