Рубрики

Следующий Большой Элемент

Для данного массива выведите Next Greater Element (NGE) для каждого элемента. Следующий больший элемент для элемента x — это первый больший элемент с правой стороны от x в массиве. Элементы, для которых не существует большего элемента, рассматривают следующий больший элемент как -1.

Примеры:

  1. Для любого массива самый правый элемент всегда имеет следующий больший элемент как -1.
  2. Для массива, который сортируется в порядке убывания, все элементы имеют следующий больший элемент как -1.
  3. Для входного массива [4, 5, 2, 25} следующие большие элементы для каждого элемента следующие.
Element       NGE
   4      -->   5
   5      -->   25
   2      -->   25
   25     -->   -1

d) Для входного массива [13, 7, 6, 12} следующие большие элементы для каждого элемента следующие.

  Element        NGE
   13      -->    -1
   7       -->     12
   6       -->     12
   12      -->     -1

Способ 1 (простой)
Используйте два цикла: внешний цикл выбирает все элементы один за другим. Внутренний цикл ищет первый больший элемент для элемента, выбранного внешним циклом. Если найден больший элемент, то этот элемент печатается следующим образом, в противном случае печатается -1.

C ++

// Простая программа на C ++ для печати
// следующие большие элементы в
// данный массив
#include<iostream>

using namespace std;

  
/ * печатает элемент и пару NGE
для всех элементов arr [] размера n * /

void printNGE(int arr[], int n)

{

    int next, i, j;

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

    {

        next = -1;

        for (j = i + 1; j < n; j++)

        {

            if (arr[i] < arr[j])

            {

                next = arr[j];

                break;

            }

        }

        cout << arr[i] << " -- " 

             << next << endl;

    }

}

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

int main()

{

    int arr[] = {11, 13, 21, 3};

    int n = sizeof(arr)/sizeof(arr[0]);

    printNGE(arr, n);

    return 0;

}

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

С

       
// Простая C программа для печати следующих больших элементов
// в заданном массиве
#include<stdio.h>

  
/ * печатает элемент и пару NGE для всех элементов
обр [] размера n * /

void printNGE(int arr[], int n)

{

    int next, i, j;

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

    {

        next = -1;

        for (j = i+1; j<n; j++)

        {

            if (arr[i] < arr[j])

            {

                next = arr[j];

                break;

            }

        }

        printf("%d -- %dn", arr[i], next);

    }

}

  

int main()

{

    int arr[]= {11, 13, 21, 3};

    int n = sizeof(arr)/sizeof(arr[0]);

    printNGE(arr, n);

    return 0;

}

Джава

// Простая Java-программа для печати далее
// большие элементы в данном массиве

  

class Main

    / * печатает элемент и пару NGE для

     все элементы arr [] размера n * /

    static void printNGE(int arr[], int n)

    {

        int next, i, j;

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

        {

            next = -1;

            for (j = i+1; j<n; j++)

            {

                if (arr[i] < arr[j])

                {

                    next = arr[j];

                    break;

                }

            }

            System.out.println(arr[i]+" -- "+next);

        }

    }

       

    public static void main(String args[])

    {

        int arr[]= {11, 13, 21, 3};

        int n = arr.length;

        printNGE(arr, n);

    }

}

питон

   
# Функция для печати элемента и пары NGE для всех элементов списка

def printNGE(arr):

  

    for i in range(0, len(arr), 1):

  

        next = -1

        for j in range(i+1, len(arr), 1):

            if arr[i] < arr[j]:

                next = arr[j]

                break

              

        print(str(arr[i]) + " -- " + str(next))

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

arr = [11,13,21,3]

printNGE(arr)

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

C #

// Простая программа на C # для печати
// большие элементы в данном массиве

using System;

  

class GFG

{

      

    / * печатает элемент и пару NGE для

    все элементы arr [] размера n * /

    static void printNGE(int []arr, int n)

    {

        int next, i, j;

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

        {

            next = -1;

            for (j = i + 1; j < n; j++)

            {

                if (arr[i] < arr[j])

                {

                    next = arr[j];

                    break;

                }

            }

            Console.WriteLine(arr[i] + " -- " + next);

        }

    }

      

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

    public static void Main()

    {

        int []arr= {11, 13, 21, 3};

        int n = arr.Length;

          

        printNGE(arr, n);

    }

}

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

PHP

<?php
// Простая PHP-программа для печати далее
// большие элементы в данном массиве

  
/ * печатает элемент и пару NGE для

   все элементы arr [] размера n * /

function printNGE($arr, $n)

{

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

    {

        $next = -1;

        for ($j = $i + 1; $j < $n; $j++)

        {

            if ($arr[$i] < $arr[$j])

            {

                $next = $arr[$j];

                break;

            }

        }

        echo $arr[$i]." -- ". $next."\n";

          

    }

}

  

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

    $arr= array(11, 13, 21, 3);

    $n = count($arr);

    printNGE($arr, $n);

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


Выход:

11 -- 13
13 -- 21
21 -- -1
3 -- -1

Сложность времени : O (n ^ 2). Наихудший случай происходит, когда все элементы отсортированы в порядке убывания.

Метод 2 (Использование стека)

  • Вставьте первый элемент в стек.
  • Выберите остальные элементы один за другим и выполните следующие шаги в цикле.
    1. Отметить текущий элемент как следующий .
    2. Если стек не пуст, сравните верхний элемент стека со следующим .
    3. Если следующий больше, чем верхний элемент, элемент Pop из стека. next — следующий больший элемент для элемента popped.
    4. Продолжайте выталкивать из стека, пока выталкиваемый элемент меньше следующего . next становится следующим большим элементом для всех таких вытолкнутых элементов
  • Наконец, нажмите следующий в стеке.
  • После завершения цикла в шаге 2 извлеките все элементы из стека и выведите -1 как следующий элемент для них.

Ниже приведен пробный запуск вышеуказанного подхода:

Ниже приведена реализация вышеуказанного подхода:

C ++

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

using namespace std;

  
/ * печатает элемент и пару NGE для всех
элементы arr [] размера n * /

void printNGE(int arr[], int n) {

  stack < int > s;

  

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

  s.push(arr[0]);

  

  // итерация для остальных элементов

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

  

    if (s.empty()) {

      s.push(arr[i]);

      continue;

    }

  

    / * если стек не пустой, то

       вытолкнуть элемент из стека.

       Если всплывающий элемент меньше

       чем дальше, то

    а) распечатать пару

    б) продолжайте появляться, пока элементы

    меньше и стек не пустой * /

    while (s.empty() == false && s.top() < arr[i])

    {         

        cout << s.top() << " --> " << arr[i] << endl;

        s.pop();

    }

  

    / * нажмите рядом со стеком, чтобы мы могли найти

    дальше больше за это * /

    s.push(arr[i]);

  }

  

  / * После перебора цикла, оставшиеся

  элементы в стеке не имеют следующего большего

  элемент, поэтому выведите -1 для них * /

  while (s.empty() == false) {

    cout << s.top() << " --> " << -1 << endl;

    s.pop();

  }

}

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

int main() {

  int arr[] = {11, 13, 21, 3};

  int n = sizeof(arr) / sizeof(arr[0]);

  printNGE(arr, n);

  return 0;

}

С

// стековая программа на C для поиска следующего большего элемента
// для всех элементов массива.
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define STACKSIZE 100

  
// структура стека

struct stack

{

    int top;

    int items[STACKSIZE];

};

  
// Функции стека, которые будут использоваться printNGE ()

void push(struct stack *ps, int x)

{

    if (ps->top == STACKSIZE-1)

    {

        printf("Error: stack overflown");

        getchar();

        exit(0);

    }

    else

    {

        ps->top += 1;

        int top = ps->top;

        ps->items [top] = x;

    }

}

  

bool isEmpty(struct stack *ps)

{

    return (ps->top == -1)? true : false;

}

  

int pop(struct stack *ps)

{

    int temp;

    if (ps->top == -1)

    {

        printf("Error: stack underflow n");

        getchar();

        exit(0);

    }

    else

    {

        int top = ps->top;

        temp = ps->items [top];

        ps->top -= 1;

        return temp;

    }

}

  
/ * печатает элемент и пару NGE для всех элементов
обр [] размера n * /

void printNGE(int arr[], int n)

{

    int i = 0;

    struct stack s;

    s.top = -1;

    int element, next;

  

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

    push(&s, arr[0]);

  

    // итерация для остальных элементов

    for (i=1; i<n; i++)

    {

        next = arr[i];

  

        if (isEmpty(&s) == false)

        {

            // если стек не пуст, то вытолкнуть элемент из стека

            element = pop(&s);

  

            / * Если всплывающий элемент меньше следующего, то

                а) распечатать пару

                б) продолжайте появляться, пока элементы меньше и

                стек не пустой * /

            while (element < next)

            {

                printf("n %d --> %d", element, next);

                if(isEmpty(&s) == true)

                   break;

                element = pop(&s);

            }

  

            / * Если элемент больше следующего, затем нажать

               элемент обратно * /

            if (element > next)

                push(&s, element);

        }

  

        / * нажмите рядом со стеком, чтобы мы могли найти

           дальше больше за это * /

        push(&s, next);

    }

  

    / * После перебора цикла, оставшиеся

       элементы в стеке не имеют следующего большего

       элемент, поэтому выведите -1 для них * /

    while (isEmpty(&s) == false)

    {

        element = pop(&s);

        next = -1;

        printf("n %d --> %d", element, next);

    }

}

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

int main()

{

    int arr[]= {11, 13, 21, 3};

    int n = sizeof(arr)/sizeof(arr[0]);

    printNGE(arr, n);

    getchar();

    return 0;

}

Джава

// Java программа для печати далее
// больший элемент, использующий стек

  

public class NGE 

{

    static class stack 

    {

        int top;

        int items[] = new int[100];

  

        // Функции стека, которые будут использоваться printNGE

        void push(int x) 

        {

            if (top == 99

            {

                System.out.println("Stack full");

            

            else 

            {

                items[++top] = x;

            }

        }

  

        int pop() 

        {

            if (top == -1

            {

                System.out.println("Underflow error");

                return -1;

            

            else 

            {

                int element = items[top];

                top--;

                return element;

            }

        }

  

        boolean isEmpty() 

        {

            return (top == -1) ? true : false;

        }

    }

  

    / * печатает элемент и пару NGE для

       все элементы arr [] размера n * /

    static void printNGE(int arr[], int n) 

    {

        int i = 0;

        stack s = new stack();

        s.top = -1;

        int element, next;

  

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

        s.push(arr[0]);

  

        // итерация для остальных элементов

        for (i = 1; i < n; i++) 

        {

            next = arr[i];

  

            if (s.isEmpty() == false

            {

                  

                // если стек не пустой, то

                // выталкиваем элемент из стека

                element = s.pop();

  

                / * Если всплывающий элемент меньше чем

                   затем а) распечатать пару б) сохранить

                   появляются в то время как элементы меньше и

                   стек не пустой * /

                while (element < next) 

                {

                    System.out.println(element + " --> " + next);

                    if (s.isEmpty() == true)

                        break;

                    element = s.pop();

                }

  

                / * Если элемент больше следующего, то

                   отодвинуть элемент назад * /

                if (element > next)

                    s.push(element);

            }

  

            / * нажмите рядом со стеком, чтобы мы могли найти следующий

               больше за это * /

            s.push(next);

        }

  

        / * После перебора цикла, оставшиеся

           элементы в стеке не имеют следующего большего

           элемент, поэтому выведите -1 для них * /

        while (s.isEmpty() == false

        {

            element = s.pop();

            next = -1;

            System.out.println(element + " -- " + next);

        }

    }

  

    public static void main(String[] args) 

    {

        int arr[] = { 11, 13, 21, 3 };

        int n = arr.length;

        printNGE(arr, n);

    }

}

  
// Спасибо Rishabh Mahrsee за предоставленный код

питон

# Программа Python для печати следующего большего элемента с использованием стека

  
# Функции стека, которые будут использоваться printNGE ()

def createStack():

    stack = []

    return stack

  

def isEmpty(stack):

    return len(stack) == 0

  

def push(stack, x):

    stack.append(x)

  

def pop(stack):

    if isEmpty(stack):

        print("Error : stack underflow")

    else:

        return stack.pop()

  
'' 'печатает элемент и пару NGE для всех элементов

   arr [] '' '

def printNGE(arr):

    s = createStack()

    element = 0

    next = 0

  

    # вставить первый элемент в стек

    push(s, arr[0])

  

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

    for i in range(1, len(arr), 1):

        next = arr[i]

  

        if isEmpty(s) == False:

  

            # если стек не пуст, то вытолкнуть элемент из стека

            element = pop(s)

  

            '' 'Если всплывающий элемент меньше следующего, то

                а) распечатать пару

                б) продолжайте появляться, пока элементы меньше и

                   стек не пуст

            while element < next :

                print(str(element)+ " -- " + str(next))

                if isEmpty(s) == True :

                    break

                element = pop(s)

  

            '' 'Если элемент больше следующего, нажмите

               элемент назад '' '

            if  element > next:

                push(s, element)

  

        '' 'нажмите рядом со стеком, чтобы мы могли найти

           дальше больше за это

        push(s, next)

  

    '' 'После перебора цикла, оставшиеся

       элементы в стеке не имеют следующего большего

       элемент, поэтому выведите -1 для них '' '

  

    while isEmpty(s) == False:

            element = pop(s)

            next = -1

            print(str(element) + " -- " + str(next))

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

arr = [11, 13, 21, 3]

printNGE(arr)

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

C #

using System;

  
// c # программа для печати далее
// больший элемент, использующий стек

  

public class NGE

{

    public class stack

    {

        public int top;

        public int[] items = new int[100];

  

        // Функции стека, которые будут использоваться printNGE

        public virtual void push(int x)

        {

            if (top == 99)

            {

                Console.WriteLine("Stack full");

            }

            else

            {

                items[++top] = x;

            }

        }

  

        public virtual int pop()

        {

            if (top == -1)

            {

                Console.WriteLine("Underflow error");

                return -1;

            }

            else

            {

                int element = items[top];

                top--;

                return element;

            }

        }

  

        public virtual bool Empty

        {

            get

            {

                return (top == -1) ? true : false;

            }

        }

    }

  

    / * печатает элемент и пару NGE для

       все элементы arr [] размера n * /

    public static void printNGE(int[] arr, int n)

    {

        int i = 0;

        stack s = new stack();

        s.top = -1;

        int element, next;

  

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

        s.push(arr[0]);

  

        // итерация для остальных элементов

        for (i = 1; i < n; i++)

        {

            next = arr[i];

  

            if (s.Empty == false)

            {

  

                // если стек не пустой, то

                // выталкиваем элемент из стека

                element = s.pop();

  

                / * Если всплывающий элемент меньше чем

                   затем а) распечатать пару б) сохранить

                   появляются в то время как элементы меньше и

                   стек не пустой * /

                while (element < next)

                {

                    Console.WriteLine(element + " --> " + next);

                    if (s.Empty == true)

                    {

                        break;

                    }

                    element = s.pop();

                }

  

                / * Если элемент больше следующего, то

                   отодвинуть элемент назад * /

                if (element > next)

                {

                    s.push(element);

                }

            }

  

            / * нажмите рядом со стеком, чтобы мы могли найти следующий

               больше за это * /

            s.push(next);

        }

  

        / * После перебора цикла, оставшиеся

           элементы в стеке не имеют следующего большего

           элемент, поэтому выведите -1 для них * /

        while (s.Empty == false)

        {

            element = s.pop();

            next = -1;

            Console.WriteLine(element + " -- " + next);

        }

    }

  

    public static void Main(string[] args)

    {

        int[] arr = new int[] {11, 13, 21, 3};

        int n = arr.Length;

        printNGE(arr, n);

    }

}

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


Выход:

 11 -- 13
 13 -- 21
 3 -- -1
 21 -- -1

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

  1. Изначально вытолкнут в стек.
  2. Выталкивается из стека при обработке следующего элемента.
  3. Отодвинут в стек, потому что следующий элемент меньше.
  4. Выскочил из стека в шаге 3 алгоритма.

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

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

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

Следующий Большой Элемент

0.00 (0%) 0 votes