bubble - encuentre la diferencia máxima entre los índices j e i tal que j> i y a[j]> a[i] en O(n)

sorting algorithms c

Question

Dada una matriz no ordenada, encuentre la diferencia max j - i entre índices tales que j > i y a[j] > a[i] en O(n) . ¿Puedo encontrar j y i usando métodos triviales en O(n^2) complejidad pero me gustaría saber cómo hacer esto en O(n) ?

Entrada: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}

Salida: 8 (j = 8, i = 0)

Entrada: {1, 2, 3, 4, 5, 6}

Salida: 5 (j = 5, i = 0)

Answer 1

Aquí hay una implementación de O (n) Python muy simple de la idea de secuencia descendente fusionada. La implementación funciona incluso en el caso de valores duplicados:

downs = [0]
for i in range(N):
if ar[i] < ar[downs[-1]]:
downs.append(i)
best = 0
i, j = len(downs)-1, N-1
while i >= 0:
if ar[downs[i]] <= ar[j]:
best = max(best, j-downs[i])
i -= 1
else:
j -= 1
print best

Answer 2

En aras de la brevedad, voy a suponer que todos los elementos son únicos. El algoritmo se puede extender para manejar casos de elementos no únicos.

Primero, observe que si y son las ubicaciones máximas y mínimas deseadas respectivamente, entonces no puede haber ninguna a[i] > a[x] e i > x , y de manera similar, no a[j] < a[y] y j < y .

Entonces escaneamos a lo largo de la matriz a y construimos una matriz S tal que S[i] contiene el índice del elemento mínimo en a[0:i] . De forma similar, una matriz T que contiene el índice del elemento máximo en a[n-1:i] (es decir, hacia atrás).

Ahora podemos ver que a[S[i]] y a[T[i]] son necesariamente secuencias decrecientes, ya que fueron el mínimo hasta i máximo desde n hasta i respectivamente.

Así que ahora tratamos de hacer un procedimiento de tipo fusión. En cada paso, si a[S[head]] < a[T[head]] , sacamos un elemento de T , de lo contrario, sacamos un elemento de S En cada uno de esos pasos, registramos la diferencia en el encabezado de S y T si a[S[head]] < a[T[head]] . El máximo de esa diferencia le da su respuesta.

EDITAR: Aquí hay un código simple en Python implementando el algoritmo.

def getMaxDist(arr):
# get minima going forward
minimum = float("inf")
minima = collections.deque()
for i in range(len(arr)):
if arr[i] < minimum:
minimum = arr[i]
minima.append((arr[i], i))
# get maxima going back
maximum = float("-inf")
maxima = collections.deque()
for i in range(len(arr)-1,0,-1):
if arr[i] > maximum:
maximum = arr[i]
maxima.appendleft((arr[i], i))
# do merge between maxima and minima
maxdist = 0
while len(maxima) and len(minima):
if maxima[0][0] > minima[0][0]:
if maxima[0][1] - minima[0][1] > maxdist:
maxdist = maxima[0][1] - minima[0][1]
maxima.popleft()
else:
minima.popleft()
return maxdist

Answer 3

Esta es una solución muy simple para O (2n) de velocidad y adicional ~ O (2n) de espacio (además de la matriz de entrada). La siguiente implementación está en C:

int findMaxDiff(int array[], int size) {
int index = 0;
int maxima[size];
int indexes[size];
while (index < size) {
int max = array[index];
int i;
for (i = index; i < size; i++) {
if (array[i] > max) {
max = array[i];
indexes[index] = i;
}
}
maxima[index] = max;
index++;
}
int j;
int result;
for (j = 0; j < size; j++) {
int max2 = 0;
if (maxima[j] - array[j] > max2) {
max2 = maxima[j] - array[j];
result = indexes[j];
}
}
return result;
}

El primer ciclo explora la matriz una vez, buscando para cada elemento el máximo de los elementos restantes a su derecha. Almacenamos también el índice relativo en una matriz separada. El segundo bucle encuentra el máximo entre cada elemento y el máximo correspondiente al lado derecho, y devuelve el índice correcto.

Answer 4

Hagamos esta simple observación: si tenemos 2 elementos a [i], a [j] con i <jy a [i] <a [j] entonces podemos estar seguros de que j no será parte de la solución como el primer elemento (puede ser el segundo, pero esa es una segunda historia) porque sería una mejor alternativa.

Lo que esto nos dice es que si construimos con avidez una secuencia decreciente de los elementos de la parte izquierda de la respuesta seguramente vendrá de allí.

Por ejemplo, para: 12 3 61 23 51 2 la secuencia decreciente codiciosa se construye así:

12 -> 12 3 -> ignoramos 61 porque es peor que 3 -> ignoramos 23 porque es peor que 3 -> ignoramos 51 porque es peor que 3 -> 12 3 2.

Entonces la respuesta contendría en el lado izquierdo 12 3 o 2.

Ahora, en un caso aleatorio, esta tiene la longitud O (log N), por lo que puede realizar una búsqueda binaria en cada elemento como la parte correcta de la respuesta y obtendrá O (N log log N) que es bueno, y si aplica el la misma lógica en la parte derecha de la cadena en un caso aleatorio podría obtener O (log ^ 2 N + N (de la lectura)) que es O (N). Pero también podemos hacer O (N) en un caso no aleatorio.

Supongamos que tenemos esta secuencia decreciente. Comenzamos desde la derecha de la cadena y hacemos lo siguiente mientras podemos emparejar la última secuencia decreciente con el número actual

1) Si encontramos una mejor solución tomando la última de la secuencia decreciente y el número actual que actualizamos la respuesta

2) Incluso si actualizamos la respuesta o no, sacamos el último elemento de la secuencia decreciente porque somos su pareja perfecta (cualquier otra coincidencia sería a la izquierda y daría una respuesta con menor j - i)

3) Repite mientras podemos emparejar estos 2

Código de ejemplo:

#include <iostream>
#include <vector>
using namespace std;
int main() {
int N; cin >> N;
vector<int> A(N + 1);
for (int i = 1; i <= N; ++i)
cin >> A[i];
// let''s solve the problem
vector<int> decreasing;
pair<int, int> answer;
// build the decreasing sequence
decreasing.push_back(1);
for (int i = 1; i <= N; ++i)
if (A[i] < A[decreasing.back()])
decreasing.push_back(i); // we work with indexes because we might have equal values
for (int i = N; i > 0; --i) {
while (decreasing.size() and A[decreasing.back()] < A[i]) { // while we can pair these 2
pair<int, int> current_pair(decreasing.back(), i);
if (current_pair.second - current_pair.first > answer.second - answer.first)
answer = current_pair;
decreasing.pop_back();
}
}
cout << "Best pair found: (" << answer.first << ", " << answer.second << ") with values (" << A[answer.first] << ", " << A[answer.second] << ")/n";
}

Más tarde Editar: Veo que dio un ejemplo: indice desde 1 para hacerlo más claro e imprimo (i, j) en lugar de (j, i). Puedes modificarlo como mejor te parezca.

Answer 5

Mi solución con O (log n) (Corrígeme aquí si me equivoco al calcular esta complejidad) tiempo ...

Idea es insertar en una BST y luego buscar nodo y si el nodo tiene un hijo derecho, recorra el subárbol derecho para calcular el nodo con índice máximo.

 import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t1 = Integer.parseInt(br.readLine());
for(int j=0;j<t1;j++){
int size = Integer.parseInt(br.readLine());
String input = br.readLine();
String[] t = input.split(" ");
Node root = new Node(Integer.parseInt(t[0]),0);
for(int i=1;i<size;i++){
Node addNode = new Node(Integer.parseInt(t[i]),i);
insertIntoBST(root,addNode);
}
for(String s: t){
Node nd = findNode(root,Integer.parseInt(s));
if(nd.right != null){
int i = nd.index;
int j1 = calculate(nd.right);
mVal = max(mVal,j1-i);
}
}
System.out.println(mVal);
mVal=0;
}
}
static int mVal =0;
public static int calculate (Node root){
if(root==null){
return -1;
}
int i = max(calculate(root.left),calculate(root.right));
return max(root.index,i);
}
public static Node findNode(Node root,int n){
if(root==null){
return null;
}
if(root.value == n){
return root;
}
Node result = findNode(root.left,n);
if(result ==null){
result = findNode(root.right,n);
}
return result;
}
public static int max(int a , int b){
return a<b?b:a;
}
public static class Node{
Node left;
Node right;
int value;
int index;
public Node(int value,int index){
this.value = value;
this.index = index;
}
}
public static void insertIntoBST(Node root, Node addNode){
if(root.value< addNode.value){
if(root.right!=null){
insertIntoBST(root.right,addNode);
}else{
root.right = addNode;
}
}
if(root.value>=addNode.value){
if(root.left!=null){
insertIntoBST(root.left,addNode);
}else{
root.left =addNode;
}
}
}
}

Answer 6

Para resolver este problema, necesitamos obtener dos índices óptimos de arr []: índice izquierdo iy índice derecho j. Para un elemento arr [i], no necesitamos considerar arr [i] para índice izquierdo si hay un elemento más pequeño que arr [i] en el lado izquierdo de arr [i]. De forma similar, si hay un elemento mayor en el lado derecho de arr [j], entonces no es necesario considerar esto j para el índice correcto. Así que construimos dos matrices auxiliares LMin [] y RMax [] tales que LMin [i] contiene el elemento más pequeño en el lado izquierdo de arr [i] incluyendo arr [i], y RMax [j] tiene el elemento más grande en el lado derecho de arr [j] incluyendo arr [j]. Después de construir estas dos matrices auxiliares, recorremos ambas matrices de izquierda a derecha. Mientras atravesamos LMin [] y RMa [] si vemos que LMin [i] es mayor que RMax [j], entonces debemos avanzar en LMin [] (o hacemos i ++) porque todos los elementos a la izquierda de LMin [i] son mayor que o igual a LMin [i]. De lo contrario, debemos avanzar en RMax [j] para buscar un mayor valor j - i. Aquí está el código c ejecutándose en O (n) tiempo:

#include <stdio.h>
#include <stdlib.h>
/* Utility Functions to get max and minimum of two integers */
int max(int x, int y)
{
return x > y? x : y;
}
int min(int x, int y)
{
return x < y? x : y;
}
/* For a given array arr[], returns the maximum j – i such that
arr[j] > arr[i] */
int maxIndexDiff(int arr[], int n)
{
int maxDiff;
int i, j;
int *LMin = (int *)malloc(sizeof(int)*n);
int *RMax = (int *)malloc(sizeof(int)*n);
/* Construct LMin[] such that LMin[i] stores the minimum value
from (arr[0], arr[1], ... arr[i]) */
LMin[0] = arr[0];
for (i = 1; i < n; ++i)
LMin[i] = min(arr[i], LMin[i-1]);
/* Construct RMax[] such that RMax[j] stores the maximum value
from (arr[j], arr[j+1], ..arr[n-1]) */
RMax[n-1] = arr[n-1];
for (j = n-2; j >= 0; --j)
RMax[j] = max(arr[j], RMax[j+1]);
/* Traverse both arrays from left to right to find optimum j - i
This process is similar to merge() of MergeSort */
i = 0, j = 0, maxDiff = -1;
while (j < n && i < n)
{
if (LMin[i] < RMax[j])
{
maxDiff = max(maxDiff, j-i);
j = j + 1;
}
else
i = i+1;
}
return maxDiff;
}
/* Driver program to test above functions */
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6};
int n = sizeof(arr)/sizeof(arr[0]);
int maxDiff = maxIndexDiff(arr, n);
printf("/n %d", maxDiff);
getchar();
return 0;
}

Answer 7

Podemos evitar comprobar toda la matriz comenzando desde la diferencia máxima de ji y comparando arr[j]>arr[i] para todas las posibles combinaciones j e i para esa diferencia máxima particular Siempre que obtengamos una combinación de (j,i) con arr[j]>arr[i] podemos salir del ciclo

Ejemplo: en una matriz de {2,3,4,5,8,1} primer código verificará la diferencia máxima 5(5-0) es decir (arr[0],arr[5]) , si arr[5]>arr[0] saldrá de lo contrario tomará combinaciones de max diff 4 (5,1) and (4,0) ie arr[5],arr[1] and arr[4],arr[0]

int maxIndexDiff(int arr[], int n)
{
int maxDiff = n-1;
int i, j;
while (maxDiff>0)
{
j=n-1;
while(j>=maxDiff)
{
i=j-maxDiff;
if(arr[j]>arr[i])
{
return maxDiff;
}
j=j-1;
}
maxDiff=maxDiff-1;
}
return -1;
}`

https://ide.geeksforgeeks.org/cjCW3wXjcj

Answer 8

Puedo pensar en una mejora sobre O (n ^ 2), pero necesito verificar si esto es O (n) en el peor de los casos o no.

• Cree una variable BestSoln=0; y recorra la matriz para el primer elemento y almacene la mejor solución para el primer elemento, es decir, bestSoln=k; .
• Ahora, para el segundo elemento, considere solo los elementos que están a k distancias del segundo elemento.
• Si BestSol n en este caso es mejor que la primera iteración, reemplácelo de otra forma, déjalo así. Sigue iterando por otros elementos.

Se puede mejorar aún más si almacenamos el elemento máximo para cada subcampo empezando desde i hasta el final. Esto se puede hacer en O (n) atravesando la matriz desde el final. Si un elemento en particular es más que su máximo local, entonces no hay necesidad de hacer una evaluación para este elemento.

Entrada:

{9, 2, 3, 4, 5, 6, 7, 8, 18, 0}

crear una matriz máxima local para esta matriz:

[18,18,18,18,18,18,18,0,0] O(n).

Ahora, recorra la matriz de 9, aquí la mejor solución será i=0,j=8 . Ahora, para el segundo elemento o después de él, no necesitamos evaluarlo. y la mejor solución es i=0,j=8 .

Pero supongamos que la matriz es Entrada:

{19, 2, 3, 4, 5, 6, 7, 8, 18, 0,4}

Matriz máxima local [18,18,18,18,18,18,18,0,0], entonces en la primera iteración no es necesario evaluar ya que el máximo local es menor que el elem actual.

Ahora, para la segunda iteración, la mejor solución es, i=1,j=10 . Ahora, para otros elementos, no es necesario considerar la evaluación, ya que no pueden ofrecer la mejor solución.

Déjame saber tu opinión sobre tu caso de uso para el cual mi solución no es aplicable.

Answer 9

Un algoritmo simplificado de la respuesta de Subhasis Das:

# assume list is not empty
max_dist = 0
acceptable_min = (0, arr[0])
acceptable_max = (0, arr[0])
min = (0, arr[0])
for i in range(len(arr)):
if arr[i] < min[1]:
min = (i, arr[i])
elif arr[i] - min[1] > max_dist:
max_dist = arr[i] - min[1]
acceptable_min = min
acceptable_max = (i, arr[i])
# acceptable_min[0] is the i
# acceptable_max[0] is the j
# max_dist is the max difference

Answer 10

Versión simplificada de la respuesta Subhasis Das utilizando matrices auxiliares.

def maxdistance(nums):
n = len(nums)
minima ,maxima = [None]*n, [None]*n
minima[0],maxima[n-1] = nums[0],nums[n-1]
for i in range(1,n):
minima[i] = min(nums[i],minima[i-1])
for i in range(n-2,-1,-1):
maxima[i]= max(nums[i],maxima[i+1])
i,j,maxdist = 0,0,-1
while(i<n and j<n):
if minima[i] <maxima[j]:
maxdist = max(j-i,maxdist)
j = j+1
else:
i += 1
print maxdist

Answer 11

Método 1 (Simple pero ineficiente)

Ejecuta dos bucles. En el ciclo externo, selecciona elementos uno por uno desde la izquierda. En el ciclo interno, compare el elemento elegido con los elementos comenzando desde el lado derecho. Detenga el ciclo interno cuando vea un elemento mayor que el elemento elegido y siga actualizando el ji máximo hasta el momento.

#include <stdio.h>
/* For a given array arr[], returns the maximum j – i such that
arr[j] > arr[i] */
int maxIndexDiff(int arr[], int n)
{
int maxDiff = -1;
int i, j;
for (i = 0; i < n; ++i)
{
for (j = n-1; j > i; --j)
{
if(arr[j] > arr[i] && maxDiff < (j - i))
maxDiff = j - i;
}
}
return maxDiff;
}
int main()
{
int arr[] = {9, 2, 3, 4, 5, 6, 7, 8, 18, 0};
int n = sizeof(arr)/sizeof(arr[0]);
int maxDiff = maxIndexDiff(arr, n);
printf("/n %d", maxDiff);
getchar();
return 0;
}

Complejidad del tiempo: O (n ^ 2)

Método 2 (Eficiente)

Para resolver este problema, necesitamos obtener dos índices óptimos de arr []: índice izquierdo iy índice derecho j. Para un elemento arr [i], no necesitamos considerar arr [i] para índice izquierdo si hay un elemento más pequeño que arr [i] en el lado izquierdo de arr [i].
De forma similar, si hay un elemento mayor en el lado derecho de arr [j], entonces no es necesario considerar esto j para el índice correcto. Así que construimos dos matrices auxiliares LMin [] y RMax [] tales que LMin [i] contiene el elemento más pequeño en el lado izquierdo de arr [i] incluyendo arr [i], y RMax [j] tiene el elemento más grande en el lado derecho de arr [j] incluyendo arr [j].
Después de construir estas dos matrices auxiliares, recorremos ambas matrices de izquierda a derecha. Mientras atravesamos LMin [] y RMa [] si vemos que LMin [i] es mayor que RMax [j], entonces debemos avanzar en LMin [] (o hacemos i ++) porque todos los elementos a la izquierda de LMin [i] son mayor que o igual a LMin [i]. De lo contrario, debemos avanzar en RMax [j] para buscar un mayor valor j - i.

#include <stdio.h>
/* Utility Functions to get max and minimum of two integers */
int max(int x, int y)
{
return x > y? x : y;
}
int min(int x, int y)
{
return x < y? x : y;
}
/* For a given array arr[], returns the maximum j – i such that
arr[j] > arr[i] */
int maxIndexDiff(int arr[], int n)
{
int maxDiff;
int i, j;
int *LMin = (int *)malloc(sizeof(int)*n);
int *RMax = (int *)malloc(sizeof(int)*n);
/* Construct LMin[] such that LMin[i] stores the minimum value
from (arr[0], arr[1], ... arr[i]) */
LMin[0] = arr[0];
for (i = 1; i < n; ++i)
LMin[i] = min(arr[i], LMin[i-1]);
/* Construct RMax[] such that RMax[j] stores the maximum value
from (arr[j], arr[j+1], ..arr[n-1]) */
RMax[n-1] = arr[n-1];
for (j = n-2; j >= 0; --j)
RMax[j] = max(arr[j], RMax[j+1]);
/* Traverse both arrays from left to right to find optimum j - i
This process is similar to merge() of MergeSort */
i = 0, j = 0, maxDiff = -1;
while (j < n && i < n)
{
if (LMin[i] < RMax[j])
{
maxDiff = max(maxDiff, j-i);
j = j + 1;
}
else
i = i+1;
}
return maxDiff;
}
/* Driver program to test above functions */
int main()
{
int arr[] = {9, 2, 3, 4, 5, 6, 7, 8, 18, 0};
int n = sizeof(arr)/sizeof(arr[0]);
int maxDiff = maxIndexDiff(arr, n);
printf("/n %d", maxDiff);
getchar();
return 0;
}

Complejidad del tiempo: O (n)
Espacio Auxiliar: O (n)
Fuente geeksforgeeks