Algoritmo para encontrar números altos/bajos con a lo sumo 1.5n comparaciones

Question

He estado pensando en esta pregunta de tarea por un momento. Dada una matriz numérica de tamaño n, diseñe un algoritmo que encuentre los valores altos y bajos con, como máximo, 1,5n de comparaciones.

Mi primer intento fue

int high=0 
int low= Number.MaxValue //problem statement is unclear on what type of number to use 
Number numList[0 . . n] //number array, assuming unsorted 

for (i=0, i < n, i++) { 
    if (numList[i] > high) 
    high = numList[i] 

    else if (numList[i] < low) 
    low = numList[i] 

} 

Mi problema es cada iteración del bucle tiene una de tres posibilidades:

• de bajo valor se encuentra - 1 comparación hecha
• alto valor se encuentra - 2 comparaciones hechas
• ninguna se encuentra - 2 comparaciones hechas

Por lo tanto, para un recorrido completo de la matriz, se pueden hacer un máximo de 2n comparaciones, lo cual está muy lejos del requisito máximo de 1.5n de las comparaciones.

Answer 1

Comience con un par de números y encuentre min local y máximo (n/2 comparaciones). A continuación, encuentre el máximo global a partir de n/2 máximos locales (n/2 comparaciones), y de forma similar global min de minutos locales (n/2 comparaciones). Comparaciones totales: 3 * n/2!

For i in 0 to n/2: #n/2 comparisons 
    if x[2*i]>x[2*i+1]: 
     swap(x,2*i,2*i+1) 

global_min = min(x[0], x[2], ...) # n/2 comparisons 
global_max = max(x[1], x[3], ...) # n/2 comparisons 

Tenga en cuenta que la solución anterior cambia la matriz. Solución alternativa:

Initialize min and max 
For i = 0 to n/2: 
    if x[2*i]<x[2*i+1]: 
     if x[2*i]< min: 
      min = x[2*i] 
     if x[2*i+1]> max: 
      max = x[2*i+1] 
    else: 
     if x[2*i+1]< min: 
      min = x[2*i+1] 
     if x[2*i]> max: 
      max = x[2*i] 

Answer 2

Ésta es la misma respuesta que ElKamina pero como yo ya había empezado a escribir el código de pseudo pensé que termine y que lo ponga.

La idea es comparar pares de valores (n/2 comparaciones) para obtener una matriz de valores altos y una matriz de valores bajos. Con cada una de esas matrices, nuevamente comparamos pares de valores (2 * n/2 comparaciones) para obtener los valores más altos y más bajos, respectivamente.

n/2 + 2*n/2 = 1.5n comparisons 

Aquí está el pseudocódigo:

int[] highNumList; 
int[] lowNumList; 

for (i = 0, i < n, i+=2) 
{ 
    a = numList[i]; 
    b = numList[i+1]; 
    if (a > b) 
    { 
     highNumList.Add(a); 
     lowNumlist.Add(b); 
    } 
    else 
    { 
     highNumlist.Add(b); 
     lowNumList.Add(a); 
    } 
} 

int high = highNumList[0]; 
int low = lowNumList[0]; 

for (i = 0, i < n/2, i+=2) 
{ 
    if (highNumList[i] < highNumList[i+1]) 
     high = highNumList[i+1] 
    if (lowNumList[i] > lowNumList[i+1]) 
     low = lowNumList[i+1] 
} 

Este código no tiene en cuenta n no ser uniforme o la matriz inicial de estar vacío.

Answer 3

Esta es una pregunta que tuve durante una entrevista y encontré la respuesta con una pequeña pista del entrevistador que era "¿Cómo se comparan dos números?" (realmente ayudó).

Aquí está la explicación:

Digamos que tengo 100 números (se puede sustituir fácilmente por n, pero que funcione mejor para el ejemplo si n es un número par). Lo que hago es dividirlo en 50 listas de 2 números. Para cada pareja hago una comparación y termino (lo que hace 50 comparaciones por ahora), entonces solo tengo que encontrar el mínimo de los mínimos (que son 49 comparaciones) y el máximo de los máximos (que son 49 comparaciones también)) de modo que tenemos que hacer 49 + 49 + 50 = 148 comparaciones. ¡Terminamos!

Observación: para encontrar el mínimo se procede de la siguiente manera (en pseudocódigo):

n=myList.size(); 
    min=myList[0]; 
    for (int i(1);i<n-1;i++) 
    { 
    if (min>myList[i]) min=myList[i]; 
    } 
    return min; 

Y lo encontramos en (1-n) comparaciones.El código es casi el mismo para el máximo.

Answer 4

Sé que esto ya ha sido respondido, pero en caso de que alguien esté buscando otra manera de pensar sobre esto. Esta respuesta es similar a Lester's, pero puede manejar valores impares de n sin romper y aún hará como máximo 1.5n comparaciones. El secreto está en el módulo. ;)

Como efecto colateral de garantizar que colocamos el último valor en la matriz adecuada, el segundo elemento en la lista dada se comparará y colocará dos veces. Sin embargo, dado que no estamos cambiando la matriz original y solo estamos interesados ​​en lo alto y bajo del conjunto, esto realmente no hace la diferencia.

Initialize lowArray and highArray 
Initialize subArrayCounter to 0 

For i = 0; i < n; i+=2 
    X = givenList[i]; 
    Y = givenList[(i+1)%n]; 
    If(x < y) 
     lowArray[subArrayCounter] = x; 
     highArray[subArrayCounter] = y; 
     subArrayCounter++; 
    else 
     lowArray[subArrayCounter] = y; 
     highArray[subArrayCounter] = x; 
     subArrayCounter++; 

Initialize low to lowArray[0]; 
Initialize high to highArray[0]; 

For i = 1; i < lowArray.length; i++ 
    If(lowArray[i] < low) 
     Low = lowArray[i]; 

For i = 1; i < highArray.length; i++ 
    If(highArray[i] > high) 
     High = highArray[i]