Найдите следующий по величине элемент в круговом массиве

Опубликовано: 5 Января, 2022

Учитывая круговой массив arr [] из N целых чисел, такой, что последний элемент данного массива находится рядом с первым элементом массива, задача состоит в том, чтобы напечатать следующий больший элемент в этом круговом массиве. Элементы, для которых не существует большего элемента, считают следующий больший элемент как «-1» .

Примеры:

Input: arr[] = {5, 6, 7} 
Output: {6, 7, -1} 
Explanation: 
Next Greater Element for 5 is 6, for 6 is 7, and for 7 is -1 as we don’t have any element greater than itself so its -1.

Input: arr[] = {4, -2, 5, 8} 
Output: {5, 5, 8, -1} 
Explanation: 
Next Greater Element for 4 is 5, for -2 its 5, for 5 is 8, and for 8 is -1 as we don’t have any element greater than itself so its -1, and for 3 its 4. 

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: эту проблему можно решить с помощью жадного подхода. Ниже приведены шаги:

  • Чтобы свойство кругового массива было действительным, снова добавьте заданные элементы массива в тот же массив.

Например:

Let arr[] = {1, 4, 3} 
After appending the same set of elements arr[] becomes 
arr[] = {1, 4, 3, 1, 4, 3} 

  • Найдите следующий больший элемент, пока не сформируется N элементов в указанном выше массиве.
  • Если найден какой-либо больший элемент, выведите этот элемент, иначе выведите «-1» .

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

C ++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the NGE
void printNGE( int A[], int n)
{
// Formation of cicular array
int arr[2 * n];
// Append the given array element twice
for ( int i = 0; i < 2 * n; i++)
arr[i] = A[i % n];
int next, i, j;
// Iterate for all the
// elements of the array
for (i = 0; i < n; i++) {
// Initialise NGE as -1
next = -1;
for (j = i + 1; j < 2 * n; j++) {
// Checking for next
// greater element
if (arr[i] < arr[j]) {
next = arr[j];
break ;
}
}
// Print the updated NGE
cout << next << ", " ;
}
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 1, 2, 1 };
int N = sizeof (arr) / sizeof (arr[0]);
// Function call
printNGE(arr, N);
return 0;
}

Джава

// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the NGE
static void printNGE( int []A, int n)
{
// Formation of cicular array
int []arr = new int [ 2 * n];
// Append the given array element twice
for ( int i = 0 ; i < 2 * n; i++)
arr[i] = A[i % n];
int next;
// Iterate for all the
// elements of the array
for ( int i = 0 ; i < n; i++)
{
// Initialise NGE as -1
next = - 1 ;
for ( int j = i + 1 ; j < 2 * n; j++)
{
// Checking for next
// greater element
if (arr[i] < arr[j])
{
next = arr[j];
break ;
}
}
// Print the updated NGE
System.out.print(next + ", " );
}
}
// Driver Code
public static void main(String args[])
{
// Given array arr[]
int []arr = { 1 , 2 , 1 };
int N = arr.length;
// Function call
printNGE(arr, N);
}
}
// This code is contributed by Code_Mech

Python3

# Python3 program for the above approach
# Function to find the NGE
def printNGE(A, n):
# Formation of cicular array
arr = [ 0 ] * ( 2 * n)
# Append the given array
# element twice
for i in range ( 2 * n):
arr[i] = A[i % n]
# Iterate for all the
# elements of the array
for i in range (n):
# Initialise NGE as -1
next = - 1
for j in range (i + 1 , 2 * n):
# Checking for next
# greater element
if (arr[i] < arr[j]):
next = arr[j]
break
# Print the updated NGE
print ( next , end = ", " )
# Driver code
if __name__ = = '__main__' :
# Given array arr[]
arr = [ 1 , 2 , 1 ]
N = len (arr)
# Function call
printNGE(arr, N)
# This code is contributed by Shivam Singh

C #

// C# program for the above approach
using System;
class GFG{
// Function to find the NGE
static void printNGE( int []A, int n)
{
// Formation of cicular array
int []arr = new int [2 * n];
// Append the given array element twice
for ( int i = 0; i < 2 * n; i++)
arr[i] = A[i % n];
int next;
// Iterate for all the
// elements of the array
for ( int i = 0; i < n; i++)
{
// Initialise NGE as -1
next = -1;
for ( int j = i + 1; j < 2 * n; j++)
{
// Checking for next
// greater element
if (arr[i] < arr[j])
{
next = arr[j];
break ;
}
}
// Print the updated NGE
Console.Write(next + ", " );
}
}
// Driver Code
public static void Main()
{
// Given array arr[]
int []arr = { 1, 2, 1 };
int N = arr.Length;
// Function call
printNGE(arr, N);
}
}
// This code is contributed by Code_Mech

Javascript

<script>
// JavaScript program for the above approach
// Function to find the NGE
function prletNGE(A, n)
{
// Formation of cicular array
let arr = Array.from({length: 2 * n}, (_, i) => 0);
// Append the given array element twice
for (let i = 0; i < 2 * n; i++)
arr[i] = A[i % n];
let next;
// Iterate for all the
// elements of the array
for (let i = 0; i < n; i++)
{
// Initialise NGE as -1
next = -1;
for (let j = i + 1; j < 2 * n; j++)
{
// Checking for next
// greater element
if (arr[i] < arr[j])
{
next = arr[j];
break ;
}
}
// Prlet the updated NGE
document.write(next + ", " );
}
}
// Driver Code
// Given array arr[]
let arr = [ 1, 2, 1 ];
let N = arr.length;
// Function call
prletNGE(arr, N);
</script>
Выход
 2, -1, 2,

Этот подход занимает время O (n 2 ), но требует дополнительного пространства порядка O (n).

Экономичное решение - иметь дело с круговыми массивами, использующими один и тот же массив. Если тщательное наблюдение выполняется через массив, то после n-го индекса следующий индекс всегда начинается с 0, поэтому, используя оператор mod , мы можем легко получить доступ к элементам кругового списка, если мы используем (i)% n и запустите цикл от i-го индекса до n + i-го индекса, и применив мод, мы можем выполнить обход в круговом массиве внутри данного массива без использования лишнего пространства.

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

C ++

// C++ program to demonstrate the use of circular
// array without using extra memory space
#include <bits/stdc++.h>
using namespace std;
// Function to find the Next Greater Element(NGE)
void printNGE( int A[], int n)
{
int k;
for ( int i = 0; i < n; i++) {
// Initialise k as -1 which is printed when no NGE
// found
k = -1; //
for ( int j = i + 1; j < n + i; j++) {
if (A[i] < A[j % n]) {
printf ( "%d " , A[j % n]);
k = 1;
break ;
}
}
if (k == -1) // Gets executed when no NGE found
printf ( "-1 " );
}
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 8, 6, 7 };
int N = sizeof (arr) / sizeof (arr[0]);
// Function call
printNGE(arr, N);
return 0;
}

Джава

// Java program to demonstrate the
// use of circular array without
// using extra memory space
import java.io.*;
class GFG{
// Function to find the Next
// Greater Element(NGE)
static void printNGE( int A[], int n)
{
int k;
for ( int i = 0 ; i < n; i++)
{
// Initialise k as -1 which is
// printed when no NGE found
k = - 1 ;
for ( int j = i + 1 ; j < n + i; j++)
{
if (A[i] < A[j % n])
{
System.out.print(A[j % n] + " " );
k = 1 ;
break ;
}
}
// Gets executed when no NGE found
if (k == - 1 )
System.out.print( "-1 " );
}
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int [] arr = { 8 , 6 , 7 };
int N = arr.length;
// Function call
printNGE(arr, N);
}
}
// This code is contributed by yashbeersingh42

Python3

# Python3 program to demonstrate the use of circular
# array without using extra memory space
# Function to find the Next Greater Element(NGE)
def printNGE(A, n) :
for i in range (n) :
# Initialise k as -1 which is printed when no NGE
# found
k = - 1
for j in range (i + 1 , n + i) :
if (A[i] < A[j % n]) :
print (A[j % n], end = " " )
k = 1
break
if (k = = - 1 ) : # Gets executed when no NGE found
print ( "-1 " , end = "")
# Given array arr[]
arr = [ 8 , 6 , 7 ]
N = len (arr)
# Function call
printNGE(arr, N)
# This code is contributed by divyeshrabadia07

C #

// C# program to demonstrate the
// use of circular array without
// using extra memory space
using System;
class GFG {
// Function to find the Next
// Greater Element(NGE)
static void printNGE( int [] A, int n)
{
int k;
for ( int i = 0; i < n; i++)
{
// Initialise k as -1 which is
// printed when no NGE found
k = -1;
for ( int j = i + 1; j < n + i; j++)
{
if (A[i] < A[j % n])
{
Console.Write(A[j % n] + " " );
k = 1;
break ;
}
}
// Gets executed when no NGE found
if (k == -1)
Console.Write( "-1 " );
}
}
static void Main()
{
// Given array arr[]
int [] arr = { 8, 6, 7 };
int N = arr.Length;
// Function call
printNGE(arr, N);
}
}
// This code is contributed by divyesh072019


Выход
 -1 7 8

Сложность времени: O (n 2 )
Вспомогательное пространство: O (1)

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Статьи Алгоритмы

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Онлайн-обменники: быстрый и удобный способ конвертации активов в современном мире
17 Апреля, 2024
Лучшие онлайн-курсы по WordPress: рейтинг 2024
29 Марта, 2024
Для кого буду полезны услуги SMS-центра
24 Марта, 2024
Что такое экспертиза исходного кода и как ее проводят?
3 Марта, 2024
Как добавить деньги на счет аккаунта Steam через криптовалюту
20 Февраля, 2024
Заказать докторскую диссертацию на заказ
30 Января, 2024
Купить лайки в ВК: зачем, сколько и где
19 Января, 2024
Как добавить деньги на свой аккаунт в Steam и начать покупать игры и контент
12 Января, 2024