arrays - una - sacar maximo y minimo de un array java

Cómo encontrar max. y min. en conjunto utilizando comparaciones mínimas?

Question

Esta es una pregunta de entrevista: dado un conjunto de números enteros, encuentre el máximo. y min. usando comparaciones mínimas.

Obviamente, puedo recorrer el array dos veces y usar ~2n comparaciones en el peor de los casos, pero me gustaría hacerlo mejor.

Answer 1

¡La fuerza bruta es MÁS RÁPIDA!

Me encantaría que alguien me muestre el error de mis caminos, aquí, pero, ...

Comparé los tiempos reales de ejecución del método de la fuerza bruta contra el (más hermoso) divide y vencer recursivo. Resultados típicos (en 10,000,000 llamadas a cada función):

Brute force :
0.657 seconds 10 values => 16 comparisons. Min @ 8, Max @ 10
0.604 seconds 1000000 values => 1999985 comparisons. Min @ 983277, Max @ 794659
Recursive :
1.879 seconds 10 values => 13 comparisons. Min @ 8, Max @ 10
2.041 seconds 1000000 values => 1499998 comparisons. Min @ 983277, Max @ 794659

Sorprendentemente, el método de fuerza bruta fue aproximadamente 2.9 veces más rápido para una matriz de 10 elementos, y 3.4 veces más rápido para una matriz de 1.000.000 de elementos.

Evidentemente, el número de comparaciones no es el problema, sino posiblemente el número de reasignaciones y la sobrecarga de llamar a una función recursiva (lo que podría explicar por qué 1,000,000 valores se ejecutan más lento que 10 valores).

Advertencias: Hice esto en VBA, no en C, y estaba comparando números de doble precisión y devolviendo el índice a la matriz de los valores Min y Max.

Aquí está el código que utilicé (la clase cPerformanceCounter no está incluida aquí, pero usa QueryPerformanceCounter para el tiempo de alta resolución):

Option Explicit
''2014.07.02
Private m_l_NumberOfComparisons As Long
Sub Time_MinMax()
Const LBOUND_VALUES As Long = 1
Dim l_pcOverall As cPerformanceCounter
Dim l_d_Values() As Double
Dim i As Long, _
k As Long, _
l_l_UBoundValues As Long, _
l_l_NumberOfIterations As Long, _
l_l_IndexOfMin As Long, _
l_l_IndexOfMax As Long
Set l_pcOverall = New cPerformanceCounter
For k = 1 To 2
l_l_UBoundValues = IIf(k = 1, 10, 1000000)
ReDim l_d_Values(LBOUND_VALUES To l_l_UBoundValues)
''Assign random values
Randomize ''1 ''1 => the same random values to be used each time
For i = LBOUND_VALUES To l_l_UBoundValues
l_d_Values(i) = Rnd
Next i
For i = LBOUND_VALUES To l_l_UBoundValues
l_d_Values(i) = Rnd
Next i
''This keeps the total run time in the one-second neighborhood
l_l_NumberOfIterations = 10000000 / l_l_UBoundValues
''——————— Time Brute Force Method —————————————————————————————————————————
l_pcOverall.RestartTimer
For i = 1 To l_l_NumberOfIterations
m_l_NumberOfComparisons = 0
IndexOfMinAndMaxDoubleBruteForce _
l_d_Values, _
LBOUND_VALUES, _
l_l_UBoundValues, _
l_l_IndexOfMin, _
l_l_IndexOfMax
Next
l_pcOverall.ElapsedSecondsDebugPrint _
3.3, , _
" seconds Brute-Force " & l_l_UBoundValues & " values => " _
& m_l_NumberOfComparisons & " comparisons. " _
& " Min @ " & l_l_IndexOfMin _
& ", Max @ " & l_l_IndexOfMax, _
True
''——————— End Time Brute Force Method —————————————————————————————————————
''——————— Time Brute Force Using Individual Calls —————————————————————————
l_pcOverall.RestartTimer
For i = 1 To l_l_NumberOfIterations
m_l_NumberOfComparisons = 0
l_l_IndexOfMin = IndexOfMinDouble(l_d_Values)
l_l_IndexOfMax = IndexOfMaxDouble(l_d_Values)
Next
l_pcOverall.ElapsedSecondsDebugPrint _
3.3, , _
" seconds Individual " & l_l_UBoundValues & " values => " _
& m_l_NumberOfComparisons & " comparisons. " _
& " Min @ " & l_l_IndexOfMin _
& ", Max @ " & l_l_IndexOfMax, _
True
''——————— End Time Brute Force Using Individual Calls —————————————————————
''——————— Time Recursive Divide and Conquer Method ————————————————————————
l_pcOverall.RestartTimer
For i = 1 To l_l_NumberOfIterations
m_l_NumberOfComparisons = 0
IndexOfMinAndMaxDoubleRecursiveDivideAndConquer _
l_d_Values, _
LBOUND_VALUES, _
l_l_UBoundValues, _
l_l_IndexOfMin, l_l_IndexOfMax
Next
l_pcOverall.ElapsedSecondsDebugPrint _
3.3, , _
" seconds Recursive " & l_l_UBoundValues & " values => " _
& m_l_NumberOfComparisons & " comparisons. " _
& " Min @ " & l_l_IndexOfMin _
& ", Max @ " & l_l_IndexOfMax, _
True
''——————— End Time Recursive Divide and Conquer Method ————————————————————
Next k
End Sub
''Recursive divide and conquer
Sub IndexOfMinAndMaxDoubleRecursiveDivideAndConquer( _
i_dArray() As Double, _
i_l_LBound As Long, _
i_l_UBound As Long, _
o_l_IndexOfMin As Long, _
o_l_IndexOfMax As Long)
Dim l_l_IndexOfLeftMin As Long, _
l_l_IndexOfLeftMax As Long, _
l_l_IndexOfRightMin As Long, _
l_l_IndexOfRightMax As Long, _
l_l_IndexOfMidPoint As Long
If (i_l_LBound = i_l_UBound) Then ''Only one element
o_l_IndexOfMin = i_l_LBound
o_l_IndexOfMax = i_l_LBound
ElseIf (i_l_UBound = (i_l_LBound + 1)) Then ''Only two elements
If (i_dArray(i_l_LBound) > i_dArray(i_l_UBound)) Then
o_l_IndexOfMin = i_l_UBound
o_l_IndexOfMax = i_l_LBound
Else
o_l_IndexOfMin = i_l_LBound
o_l_IndexOfMax = i_l_UBound
End If
m_l_NumberOfComparisons = m_l_NumberOfComparisons + 1
Else ''More than two elements => recurse
l_l_IndexOfMidPoint = (i_l_LBound + i_l_UBound) / 2
''Find the min of the elements in the left half
IndexOfMinAndMaxDoubleRecursiveDivideAndConquer _
i_dArray, _
i_l_LBound, _
l_l_IndexOfMidPoint, _
l_l_IndexOfLeftMin, _
l_l_IndexOfLeftMax
''Find the min of the elements in the right half
IndexOfMinAndMaxDoubleRecursiveDivideAndConquer i_dArray, _
l_l_IndexOfMidPoint + 1, _
i_l_UBound, _
l_l_IndexOfRightMin, _
l_l_IndexOfRightMax
''Return the index of the lower of the two values returned
If (i_dArray(l_l_IndexOfLeftMin) > i_dArray(l_l_IndexOfRightMin)) Then
o_l_IndexOfMin = l_l_IndexOfRightMin
Else
o_l_IndexOfMin = l_l_IndexOfLeftMin
End If
m_l_NumberOfComparisons = m_l_NumberOfComparisons + 1
''Return the index of the lower of the two values returned
If (i_dArray(l_l_IndexOfLeftMax) > i_dArray(l_l_IndexOfRightMax)) Then
o_l_IndexOfMax = l_l_IndexOfLeftMax
Else
o_l_IndexOfMax = l_l_IndexOfRightMax
End If
m_l_NumberOfComparisons = m_l_NumberOfComparisons + 1
End If
End Sub
Sub IndexOfMinAndMaxDoubleBruteForce( _
i_dArray() As Double, _
i_l_LBound As Long, _
i_l_UBound As Long, _
o_l_IndexOfMin As Long, _
o_l_IndexOfMax As Long)
Dim i As Long
o_l_IndexOfMin = i_l_LBound
o_l_IndexOfMax = o_l_IndexOfMin
For i = i_l_LBound + 1 To i_l_UBound
''Usually we will do two comparisons
m_l_NumberOfComparisons = m_l_NumberOfComparisons + 2
If (i_dArray(i) < i_dArray(o_l_IndexOfMin)) Then
o_l_IndexOfMin = i
''We don''t need to do the ElseIf comparison
m_l_NumberOfComparisons = m_l_NumberOfComparisons - 1
ElseIf (i_dArray(i) > i_dArray(o_l_IndexOfMax)) Then
o_l_IndexOfMax = i
End If
Next i
End Sub
Function IndexOfMinDouble( _
i_dArray() As Double _
) As Long
Dim i As Long
On Error GoTo EWE
IndexOfMinDouble = LBound(i_dArray)
For i = IndexOfMinDouble + 1 To UBound(i_dArray)
If (i_dArray(i) < i_dArray(IndexOfMinDouble)) Then
IndexOfMinDouble = i
End If
m_l_NumberOfComparisons = m_l_NumberOfComparisons + 1
Next i
On Error GoTo 0
Exit Function
EWE:
On Error GoTo 0
IndexOfMinDouble = MIN_LONG
End Function
Function IndexOfMaxDouble( _
i_dArray() As Double _
) As Long
Dim i As Long
On Error GoTo EWE
IndexOfMaxDouble = LBound(i_dArray)
For i = IndexOfMaxDouble + 1 To UBound(i_dArray)
If (i_dArray(i) > i_dArray(IndexOfMaxDouble)) Then
IndexOfMaxDouble = i
End If
m_l_NumberOfComparisons = m_l_NumberOfComparisons + 1
Next i
On Error GoTo 0
Exit Function
EWE:
On Error GoTo 0
IndexOfMaxDouble = MIN_LONG
End Function

Answer 2

Después de leer la pregunta y las respuestas, decidí probar algunas versiones (en C #).
Pensé que el más rápido sería el de Anton Knyazyev (sin ramal), no lo está (en mi casilla).
Resultados:

/* comp. time(ns)
minmax0 3n/2 855
minmax1 2n 805
minmax2 2n 1315
minmax3 2n 685 */

¿Por qué son minmax1 y minmax3 más rápidos? Probablemente porque el "predictor de rama" hace un buen trabajo, cada iteración se presenta la oportunidad, se encuentra un nuevo mínimo (o máximo), disminuye, por lo que las predicciones mejoran.
En general, es una prueba simple. Me doy cuenta de que mis conclusiones pueden ser:
-prematuro.
- no válido para diferentes plataformas.
Digamos que son indicativos.
Editar: punto de equilibrio minmax0, minmax3: ~ 100 elementos,
10,000 elementos: minmax3 ~ 3.5 veces más rápido que minmax0.

using System;
using sw = System.Diagnostics.Stopwatch;
class Program
{
static void Main()
{
int n = 1000;
int[] a = buildA(n);
sw sw = new sw();
sw.Start();
for (int i = 1000000; i > 0; i--) minMax3(a);
sw.Stop();
Console.Write(sw.ElapsedMilliseconds);
Console.Read();
}
static int[] minMax0(int[] a) // ~3j/2 comp.
{
int j = a.Length - 1;
if (j < 2) return j < 0 ? null :
j < 1 ? new int[] { a[0], a[0] } :
a[0] < a[1] ? new int[] { a[0], a[1] } :
new int[] { a[1], a[0] };
int a0 = a[0], a1 = a[1], ai = a0;
if (a1 < a0) { a0 = a1; a1 = ai; }
int i = 2;
for (int aj; i < j; i += 2)
{
if ((ai = a[i]) < (aj = a[i + 1])) // hard to predict
{ if (ai < a0) a0 = ai; if (aj > a1) a1 = aj; }
else
{ if (aj < a0) a0 = aj; if (ai > a1) a1 = ai; }
}
if (i <= j)
{ if ((ai = a[i]) < a0) a0 = ai; else if (ai > a1) a1 = ai; }
return new int[] { a0, a1 };
}
static int[] minMax1(int[] a) // ~2j comp.
{
int j = a.Length;
if (j < 3) return j < 1 ? null :
j < 2 ? new int[] { a[0], a[0] } :
a[0] < a[1] ? new int[] { a[0], a[1] } :
new int[] { a[1], a[0] };
int a0 = a[0], a1 = a0, ai = a0;
for (int i = 1; i < j; i++)
{
if ((ai = a[i]) < a0) a0 = ai;
else if (ai > a1) a1 = ai;
}
return new int[] { a0, a1 };
}
static int[] minMax2(int[] a) // ~2j comp.
{
int j = a.Length;
if (j < 2) return j == 0 ? null : new int[] { a[0], a[0] };
int a0 = a[0], a1 = a0;
for (int i = 1, ai = a[1], aj = ai; ; aj = ai = a[i])
{
ai -= a0; a0 += ai & ai >> 31;
aj -= a1; a1 += aj & -aj >> 31;
i++; if (i >= j) break;
}
return new int[] { a0, a1 };
}
static int[] minMax3(int[] a) // ~2j comp.
{
int j = a.Length - 1;
if (j < 2) return j < 0 ? null :
j < 1 ? new int[] { a[0], a[0] } :
a[0] < a[1] ? new int[] { a[0], a[1] } :
new int[] { a[1], a[0] };
int a0 = a[0], a1 = a[1], ai = a0;
if (a1 < a0) { a0 = a1; a1 = ai; }
int i = 2;
for (j -= 2; i < j; i += 3)
{
ai = a[i + 0]; if (ai < a0) a0 = ai; if (ai > a1) a1 = ai;
ai = a[i + 1]; if (ai < a0) a0 = ai; if (ai > a1) a1 = ai;
ai = a[i + 2]; if (ai < a0) a0 = ai; if (ai > a1) a1 = ai;
}
for (j += 2; i <= j; i++)
{ if ((ai = a[i]) < a0) a0 = ai; else if (ai > a1) a1 = ai; }
return new int[] { a0, a1 };
}
static int[] buildA(int n)
{
int[] a = new int[n--]; Random rand = new Random(0);
for (int j = n; n >= 0; n--) a[n] = rand.Next(-1 * j, 1 * j);
return a;
}
}

Answer 3

Intentando mejorar la respuesta por srbh.kmr. Digamos que tenemos la secuencia:

A = [a1, a2, a3, a4, a5]

Compara a1 y a2 y calcula min12 , max12 :

if (a1 > a2)
min12 = a2
max12 = a1
else
min12 = a1
max12 = a2

Del mismo modo, calcule min34 , max34 . Como a5 está solo, mantenlo como está ...

Ahora compare min12 y min34 y calcule min14 , de manera similar calcule max14 . Finalmente compare min14 y a5 para calcular min15 . Del mismo modo, calcule max15 .

¡En total son solo 6 comparaciones!

Esta solución se puede extender a una matriz de longitud arbitraria. Probablemente se puede implementar mediante un enfoque similar a merge-sort (divide la matriz por la mitad y calcula el min max para cada mitad).

ACTUALIZACIÓN: Aquí está el código recursivo en C:

#include <stdio.h>
void minmax (int* a, int i, int j, int* min, int* max) {
int lmin, lmax, rmin, rmax, mid;
if (i == j) {
*min = a[i];
*max = a[j];
} else if (j == i + 1) {
if (a[i] > a[j]) {
*min = a[j];
*max = a[i];
} else {
*min = a[i];
*max = a[j];
}
} else {
mid = (i + j) / 2;
minmax(a, i, mid, &lmin, &lmax);
minmax(a, mid + 1, j, &rmin, &rmax);
*min = (lmin > rmin) ? rmin : lmin;
*max = (lmax > rmax) ? lmax : rmax;
}
}
void main () {
int a [] = {3, 4, 2, 6, 8, 1, 9, 12, 15, 11};
int min, max;
minmax (a, 0, 9, &min, &max);
printf ("Min : %d, Max: %d/n", min, max);
}

Ahora no puedo distinguir el número exacto de comparaciones en términos de N (la cantidad de elementos en la matriz). Pero es difícil ver cómo se puede ir por debajo de estas muchas comparaciones.

ACTUALIZACIÓN: podemos calcular el número de comparaciones como a continuación:

En la parte inferior de este árbol de cómputos, formamos pares de enteros a partir de la matriz original. Entonces tenemos N / 2 nodos de hoja. Para cada uno de estos nodos hoja, hacemos exactamente 1 comparación.

Al referirnos a las propiedades de un árbol binario perfecto , tenemos:

leaf nodes (L) = N / 2 // known
total nodes (n) = 2L - 1 = N - 1
internal nodes = n - L = N / 2 - 1

Para cada nodo interno hacemos 2 comparaciones. Por lo tanto, tenemos comparaciones N - 2 . Junto con las comparaciones N / 2 en los nodos de la hoja, tenemos (3N / 2) - 2 comparaciones totales.

Entonces, puede ser que esta sea la solución srbh.kmr implícita en su respuesta.

Answer 4

Mi enfoque de dividir y conquistar con java hasta ahora:

 public class code {
static int[] A = {444,9,8,6,199,3,0,5,3,200};
static int min = A[0], max = A[1];
static int count = 0;
public void minMax(int[] A, int i, int j) {
if(i==j) {
count = count + 2;
min = Math.min(min, A[i]);
max = Math.max(max, A[i]);
}
else if(j == i+1) {
if(A[i] > A[j]) {
count = count + 3;
min = Math.min(min, A[j]);
max = Math.max(max, A[i]);
}
else {
count = count + 3;
min = Math.min(min, A[i]);
max = Math.max(max, A[j]);
}
}
else {
minMax(A,i,(i+j)/2);
minMax(A,(i+j)/2+1,j);
}
}
public static void main(String[] args) {
code c = new code();
if(Math.min(A[0], A[1]) == A[0]) {
count++;
min = A[0];
max = A[1];
}
else {
count++;
min = A[1];
max = A[0];
}
c.minMax(A,2,A.length-1);
System.out.println("Min: "+min+" Max: "+max);
System.out.println("Total comparisons: " + count);
}
}

Answer 5

Recorra la matriz una vez, controlando los máximos y mínimos hasta el momento.

Answer 6

Un enfoque algo diferente, que utiliza la aritmética de enteros en lugar de las comparaciones (que no estaba explícitamente prohibido)

for(int i=0;i<N;i++) {
xmin += x[i]-xmin & x[i]-xmin>>31;
xmax += x[i]-xmax & xmax-x[i]>>31;
}

Answer 7

Un pseudo código simple para el algoritmo recursivo:

Function MAXMIN (A, low, high)
if (high − low + 1 = 2) then
if (A[low] < A[high]) then
max = A[high]; min = A[low].
return((max, min)).
else
max = A[low]; min = A[high].
return((max, min)).
end if
else
mid = low+high/2
(max_l , min_l ) = MAXMIN(A, low, mid).
(max_r , min_r ) =MAXMIN(A, mid + 1, high).
end if
Set max to the larger of max_l and max_r ;
likewise, set min to the smaller of min_l and min_r .
return((max, min)).

Answer 8

ir a dividir y conquistar!

1,3,2,5

para este resultado mínimo, max tomará 6 comparaciones

pero divídelos

1,3 ---> dará min 1 y max 3 en una comparación 2,5 ---> dará min 2 y max 5 en una comparación

ahora podemos comparar dos minutos (1,2) -> darán el mínimo final como 1 (una comparación) así como dos máximos (3,5) ---> darán el máximo final como 5 (una comparación)

tan totalmente cuatro comparaciones

Answer 9

#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
set<int> t;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
t.insert(x);
}
set<int>::iterator s,b;
s=t.begin();
b=--t.end();
cout<< *s<<" "<<*b<<endl;
enter code here
return 0;
}

// esto se puede hacer en log (n) complejidad !!!

Answer 10

1. Pick 2 elements(a, b), compare them. (say a > b)
2. Update min by comparing (min, b)
3. Update max by comparing (max, a)

De esta forma, harías 3 comparaciones para 2 elementos, lo que equivale a 3N/2 comparaciones totales para N elementos.

Answer 11

import java.util.*;
class Maxmin
{
public static void main(String args[])
{
int[] arr = new int[10];
Scanner in = new Scanner(System.in);
int i, min=0, max=0;
for(i=0; i<=9; i++)
{
System.out.print("Enter any number: ");
arr[i] = in.nextInt();
}
min = arr[0];
for(i=0; i<=9; i++)
{
if(arr[i] > max)
{
max = arr[i];
}
if(arr[i] < min)
{
min = arr[i];
}
}
System.out.println("Maximum is: " + max);
System.out.println("Minimum is: " + min);
}
}

Answer 12

public static int[] minMax(int[] array){
int [] empty = {-1,-1};
if(array==null || array.length==0){
return empty;
}
int lo =0, hi = array.length-1;
return minMax(array,lo, hi);
}
private static int[] minMax(int []array, int lo, int hi){
if(lo==hi){
int [] result = {array[lo], array[hi]};
return result;
}else if(lo+1==hi){
int [] result = new int[2];
result[0] = Math.min(array[lo], array[hi]);
result[1] = Math.max(array[lo], array[hi]);
return result;
}else{
int mid = lo+(hi-lo)/2;
int [] left = minMax(array, lo, mid);
int [] right = minMax(array, mid+1, hi);
int []result = new int[2];
result[0] = Math.min(left[0], right[0]);
result[1] = Math.max(left[1], right[1]);
return result;
}
}
public static void main(String[] args) {
int []array = {1,2,3,4,100};
System.out.println("min and max values are "+Arrays.toString(minMax(array)));
}