Encuentra el valor mínimo en una lista circular de enteros -- java campo con algorithm campo con array campo con binary-search camp codereview Relacionados El problema

Find the minimum value in a circular list of integers


3
vote

problema

Español

Estaba buscando algunos desafíos codificantes y esto parecía divertido para resolver. Lo probé con los siguientes valores y parece funcionar para aquellos al menos:

  • [5, 7, 8, 9, 11, 2, 3]
  • [5, 7, 1, 4]
  • [5, 7, 8, 1, 5]
  • [5, 1, 2, 3, 5]
  • [5, 5, 5]
  • [1]
  • [1, 2]
  • [2, 1]

Mi solución fue implementar una búsqueda binaria para intentar encontrar el valor más pequeño, y si ambos extremos de la Sub-Lista tienen el mismo valor, se incrementaré del valor más bajo para intentar trabajar si el valor más bajo se encuentra. en la primera o segunda mitad del sublista. No tengo un 100% seguro de que esta parte de la solución es libre de errores, así que apreciaría cualquier retroalimentación sobre eso.

Estoy buscando su opinión sobre mi lógica, ya que el estándar de codificación no me importa demasiado en este caso.

  mysqldumpslow3  
Original en ingles

I was looking up some coding challenges and this looked like a fun one to solve. I tested it with the following values and it seems to work for those at least:

  • [ 5, 7, 8, 9, 11, 2, 3 ]
  • [ 5, 7, 1, 4]
  • [ 5, 7, 8, 1, 5]
  • [ 5, 1, 2, 3, 5]
  • [ 5, 5, 5]
  • [ 1 ]
  • [ 1, 2 ]
  • [ 2, 1 ]

My solution was to implement a binary search to try and find the smallest value, and if both ends of the sub-list have the same value then I will increment from the lowest value to try and work out if the lowest value lies in the first or second half of the sublist. I am not 100% confident that this part of the solution is bug free, so would appreciate any feedback on that.

I am mostly looking for feedback on my logic, as the coding standard doesn't matter to me too much in this case.

public static int findMinimum(List<Integer> input) {   return findMinRecursive(input, 0, input.size() - 1); }  public static int findMinRecursive(List<Integer> input, int lowestIndex, int highestIndex) {   if (lowestIndex == highestIndex) {     return input.get(lowestIndex);   }   boolean lastCheck = highestIndex - lowestIndex == 1;    int offset = (highestIndex - lowestIndex) / 2;   if (input.get(highestIndex) > input.get(lowestIndex)) {     if (lastCheck) {       return input.get(lowestIndex);     }     return findMinRecursive(input, lowestIndex, highestIndex / 2);   } else if (input.get(highestIndex) < input.get(lowestIndex)) {     if (lastCheck) {       return input.get(highestIndex);     }     return findMinRecursive(input, lowestIndex + offset, highestIndex);   } else {     // If the numbers are equal we need to find out which direction has the minimum     for (int i = lowestIndex; i < highestIndex; i++) {       if (input.get(i) > input.get(lowestIndex)) {         return findMinRecursive(input, lowestIndex + offset, highestIndex);       } else if (input.get(i) < input.get(lowestIndex)) {         return input.get(i);       }     }     return input.get(lowestIndex);   } } 
           
   
   

Lista de respuestas

1
 
vote

Puede arreglar el error, que se señaló @misha, cambiando

  __slots__2  

a

  __slots__3  

Porque, si el valor a la derecha es mayor que el valor a la izquierda en la subsección que está buscando, entonces esa subsección ya está perfectamente ordenada en orden ascendente.

También creo que puede lograr una mejora muy pequeña de rendimiento si no usa tantas llamadas para obtener (). Puede almacenar los valores en las propiedades (a.k.a. Variables) primero, y luego use esas variables / propiedades en lugar de la obtención (), pero es probablemente un impulso de rendimiento casi imperceptible

 

You can fix the bug, that @Misha pointed out, by changing

    if (input.get(highestIndex) > input.get(lowestIndex)) {       if (lastCheck) {         return input.get(lowestIndex);       }       return Main.findMinRecursive(input, lowestIndex, highestIndex / 2);     } 

to

    if (input.get(highestIndex) > input.get(lowestIndex)) {       return input.get(lowestIndex);     } 

because, if the value to the right is greater than the value to the left in the subsection you are searching through, then that subsection is already perfectly sorted in ascending order.

I also think you can achieve a very tiny performance improvement if you don't use so many calls to get(). You can store the values in properties(a.k.a. variables) first, and then use those variables/properties in place of the get(), but it's probably an almost imperceptible performance boost

 
 

Relacionados problema

2  Búsqueda binaria, usando  ( Binary search using remove ) 
Soy consciente de que existe una función en la biblioteca estándar. Por favor, dame comentarios sobre buenos convenciones y estándares de codificación. fun...

5  Búsqueda binaria: primera / última / ocurrencia aleatoria  ( Binary search first last random occurrence ) 
He escrito un código para "búsqueda binaria" una lista, y devolver el primera ocurrencia del objetivo: def bsearch(a, left, right, target, first_or_last ...

2  Encontrar el subconjunto máximo de intervalos no superpuestos  ( Finding the max subset of non overlapping intervals ) 
¿Cómo podría este código ser más limpio? Creo que la forma en que manejo las interfaces y la búsqueda binaria podría mejorarse. Estoy tratando de entender cóm...

2  Eliminación de un nodo en un árbol de búsqueda binario  ( Deletion of a node in a binary search tree ) 
Estoy buscando ver si mi implementación del método de eliminación / eliminación en un árbol de búsqueda binario es suficiente, legible y se ejecuta en un tiem...

10  Encuentre el duplicado en una matriz ordenada en menos de O (n)  ( Find the duplicate in a sorted array in less than on ) 
suposiciones: La matriz está ordenada. solo hay un duplicado. La matriz solo se rellena con números [0, N], donde n es la longitud de la matriz. Eje...

7  Búsqueda binaria de Java (y obtenga índice si no está allí) Revisión  ( Java binary search and get index if not there review ) 
Quiero hacer una búsqueda binaria y si el objetivo no está allí, obtenga el índice de donde debería haber sido. Este es el código en el que se me ocurrió. P...

5  BinarySearch Kata en Ruby  ( Binarysearch kata in ruby ) 
Acabo de completar esta búsqueda binaria Kata, que tiene algunos requisitos extraños, y pasé un poco "limpiando" mi código y haciéndolo más compacto. Agradece...

5  Búsqueda binaria eficiente  ( Efficient binary search ) 
Mi implementación: 157 Implementación normal: 158 La diferencia de ser mi implementación hace una conjetura en el índice del valor en función de l...

3  ¿Es esta búsqueda binaria cerca de Idiomatic OCAML?  ( Is this binary search close to idiomatic ocaml ) 
let binsearch ~arr ~cmp x = ( let cmpx = cmp x in (* Assuming arr is ordered according to cmp, then (bs min max) is an *) (* index of a value v...

1  Retroalimentación de búsqueda binaria  ( Binary search feedback ) 
He escrito un algoritmo de búsqueda binario, pero parece ser un poco diferente a otras personas que he visto. Esperaba que la comunidad pudiera darme algunos ...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos