Dada una array arr[] de tamaño N . Para cada elemento de la array, la tarea es encontrar el índice del elemento más alejado de la array a la derecha que es más pequeño que el elemento actual. Si no existe tal número, imprima -1 .
Ejemplos:
Entrada: arr[] = {3, 1, 5, 2, 4}
Salida: 3 -1 4 -1 -1
arr[3] es el elemento más pequeño a la derecha de arr[0].
arr[4] es el elemento más pequeño a la derecha de arr[2].
Y para el resto de elementos, no hay elemento menor a su derecha.Entrada: arr[] = {1, 2, 3, 4, 0}
Salida: 4 4 4 4 -1
Enfoque 1: (Método de fuerza bruta)
Un enfoque de fuerza bruta para este problema puede ser mantener una variable idx = -1 desde el principio y para cada elemento comenzar a recorrer la misma array desde atrás hasta (i+1) el índice th. Y, si en cualquier índice j encuentra un elemento más pequeño del elemento actual, es decir, (a[i] > a[j]) salga del bucle.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the farthest
// smaller number in the right side
void farthest_min(int a[], int n)
{
for (int i = 0; i < n; i++) {
// keeping the idx = -1 from beginning
int idx = -1;
// traverse the given array backward
for (int j = n - 1; j > i; j--) {
// if found any element smaller
if (a[i] > a[j]) {
// update that index and break
idx = j;
break;
}
}
// Print the required index
cout << idx << " ";
}
}
// Driver code
int main()
{
int a[] = { 3, 1, 5, 2, 4 };
int n = sizeof(a) / sizeof(a[0]);
farthest_min(a, n);
return 0;
}
// this code is contributed by Rajdeep
Java
// Java implementation of the approach
class GFG {
// Function to find the farthest
// smaller number in the right side
static void farthest_min(int[] a, int n)
{
// To store minimum element
// in the range i to n
for (int i = 0; i < n; i++) {
// keeping the idx = -1 from beginning
int idx = -1;
for (int j = n - 1; j > i; j--) {
// if found any element smaller
if (a[i] > a[j]) {
// update that index and break
idx = j;
break;
}
}
System.out.print(idx + " ");
}
}
// Driver code
public static void main(String[] args)
{
int[] a = { 3, 1, 5, 2, 4 };
int n = a.length;
farthest_min(a, n);
}
}
// This code is contributed by Rajdeep
C#
// C# implementation of the approach
using System;
class GFG {
// Function to find the farthest
// smaller number in the right side
static void farthest_min(int[] a, int n)
{
// To store minimum element
// in the range i to n
for (int i = 0; i < n; i++) {
// keeping the idx = -1 from beginning
int idx = -1;
for (int j = n - 1; j > i; j--) {
// if found any element smaller
if (a[i] > a[j]) {
// update that index and break
idx = j;
break;
}
}
Console.Write(idx + " ");
}
}
// Driver code
public static void Main()
{
int[] a = { 3, 1, 5, 2, 4 };
int n = a.Length;
farthest_min(a, n);
}
}
// This code is contributed by Samim Hossain Mondal.
3 -1 4 -1 -1
Complejidad de tiempo: O(N^2)
Espacio auxiliar: O(1)
Enfoque 2: (Método optimizado)
Un enfoque eficiente es crear una array suffix_min[] donde suffix_min[i] almacena el elemento mínimo del subarreglo arr[i … N – 1] . Ahora, para cualquier elemento arr[i] , la búsqueda binaria se puede usar en el sufijo sufijo_min[i + 1 … N – 1] para encontrar el elemento más pequeño a la derecha de arr[i] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the farthest
// smaller number in the right side
void farthest_min(int a[], int n)
{
// To store minimum element
// in the range i to n
int suffix_min[n];
suffix_min[n - 1] = a[n - 1];
for (int i = n - 2; i >= 0; i--) {
suffix_min[i] = min(suffix_min[i + 1], a[i]);
}
for (int i = 0; i < n; i++) {
int low = i + 1, high = n - 1, ans = -1;
while (low <= high) {
int mid = (low + high) / 2;
// If current element in the suffix_min
// is less than a[i] then move right
if (suffix_min[mid] < a[i]) {
ans = mid;
low = mid + 1;
}
else
high = mid - 1;
}
// Print the required answer
cout << ans << " ";
}
}
// Driver code
int main()
{
int a[] = { 3, 1, 5, 2, 4 };
int n = sizeof(a) / sizeof(a[0]);
farthest_min(a, n);
return 0;
}
Java
// Java implementation of the approach
class GFG {
// Function to find the farthest
// smaller number in the right side
static void farthest_min(int[] a, int n)
{
// To store minimum element
// in the range i to n
int[] suffix_min = new int[n];
suffix_min[n - 1] = a[n - 1];
for (int i = n - 2; i >= 0; i--) {
suffix_min[i]
= Math.min(suffix_min[i + 1], a[i]);
}
for (int i = 0; i < n; i++) {
int low = i + 1, high = n - 1, ans = -1;
while (low <= high) {
int mid = (low + high) / 2;
// If current element in the suffix_min
// is less than a[i] then move right
if (suffix_min[mid] < a[i]) {
ans = mid;
low = mid + 1;
}
else
high = mid - 1;
}
// Print the required answer
System.out.print(ans + " ");
}
}
// Driver code
public static void main(String[] args)
{
int[] a = { 3, 1, 5, 2, 4 };
int n = a.length;
farthest_min(a, n);
}
}
// This code is contributed by ihritik
Python3
# Python3 implementation of the approach # Function to find the farthest # smaller number in the right side def farthest_min(a, n): # To store minimum element # in the range i to n suffix_min = [0 for i in range(n)] suffix_min[n - 1] = a[n - 1] for i in range(n - 2, -1, -1): suffix_min[i] = min(suffix_min[i + 1], a[i]) for i in range(n): low = i + 1 high = n - 1 ans = -1 while (low <= high): mid = (low + high) // 2 # If current element in the suffix_min # is less than a[i] then move right if (suffix_min[mid] < a[i]): ans = mid low = mid + 1 else: high = mid - 1 # Print the required answer print(ans, end=" ") # Driver code a = [3, 1, 5, 2, 4] n = len(a) farthest_min(a, n) # This code is contributed by Mohit Kumar
C#
// C# implementation of the approach
using System;
class GFG {
// Function to find the farthest
// smaller number in the right side
static void farthest_min(int[] a, int n)
{
// To store minimum element
// in the range i to n
int[] suffix_min = new int[n];
suffix_min[n - 1] = a[n - 1];
for (int i = n - 2; i >= 0; i--) {
suffix_min[i]
= Math.Min(suffix_min[i + 1], a[i]);
}
for (int i = 0; i < n; i++) {
int low = i + 1, high = n - 1, ans = -1;
while (low <= high) {
int mid = (low + high) / 2;
// If current element in the suffix_min
// is less than a[i] then move right
if (suffix_min[mid] < a[i]) {
ans = mid;
low = mid + 1;
}
else
high = mid - 1;
}
// Print the required answer
Console.Write(ans + " ");
}
}
// Driver code
public static void Main()
{
int[] a = { 3, 1, 5, 2, 4 };
int n = a.Length;
farthest_min(a, n);
}
}
// This code is contributed by ihritik
Javascript
Javascript<script>
// Javascript implementation of the approach
// Function to find the farthest
// smaller number in the right side
function farthest_min(a, n)
{
// To store minimum element
// in the range i to n
let suffix_min = new Array(n);
suffix_min[n - 1] = a[n - 1];
for (let i = n - 2; i >= 0; i--) {
suffix_min[i] = Math.min(suffix_min[i + 1], a[i]);
}
for (let i = 0; i < n; i++) {
let low = i + 1, high = n - 1, ans = -1;
while (low <= high) {
let mid = Math.floor((low + high) / 2);
// If current element in the suffix_min
// is less than a[i] then move right
if (suffix_min[mid] < a[i]) {
ans = mid;
low = mid + 1;
}
else
high = mid - 1;
}
// Print the required answer
document.write(ans + " ");
}
}
// Driver code
let a = [ 3, 1, 5, 2, 4 ];
let n = a.length;
farthest_min(a, n);
//This code is contributed by Mayank Tyagi
</script>
3 -1 4 -1 -1
Complejidad de tiempo: O(N* log(N) )
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA