Encuentra el número más pequeño en Arreglo rotativo ordenado

Question

Me encontré con esta pregunta en una entrevista. Por favor, ayúdame a obtener la solución.

La pregunta es:

Usted ha ordenado conjunto giratorio, i. mi. la matriz contiene elementos que se clasifican y se puede rotar circularmente, como si los elementos en la matriz fueran [5,6,10,19,20,29] y luego la matriz de la primera vuelta se convierte en [29,5,6,10,19] , 20] y en la segunda vez se convierte en [20,29,5,6,10,19] y así sucesivamente.

Por lo tanto, debe encontrar el elemento más pequeño en la matriz en cualquier punto. No se le proporcionará el número de veces que se gira la matriz. Acabo de dar los elementos de matriz girados y descubrir el más pequeño entre ellos. En este caso, la salida debe ser 5.

Answer 1

Método 1:

Usted puede hacer esto en O(logN) tiempo.

utilizar una búsqueda binaria modificada para encontrar el punto de rotación que es un índice i tal que
arr[i] > arr[i+1].

Ejemplo:

[6,7,8,9,1,2,3,4,5] 
    ^
     i 

Las dos sub-series
(arr[1], arr[2], .., arr[i]) y
(arr[i+1], arr[i+2], ..., arr[n]) están ordenadas.

La respuesta es min(arr[1], arr[i+1])

Método 2:

Al dividir la ordenados, matriz rotada en dos mitades (arr[1],..,arr[mid]) y (arr[mid+1],..,arr[n]), uno de ellos siempre se ordena y el otro siempre tiene el min. Podemos utilizar directamente una búsqueda binaria modificada para seguir buscando en el medio sin clasificar

// index of first element 
l = 0 

// index of last element. 
h = arr.length - 1 

// always restrict the search to the unsorted 
// sub-array. The min is always there. 
while (arr[l] > arr[h]) { 
     // find mid. 
     mid = (l + h)/2 
     // decide which sub-array to continue with. 
     if (arr[mid] > arr[h]) { 
       l = mid + 1 
     } else { 
       h = mid 
     } 
} 
// answer 
return arr[l] 

Answer 2

El algorihtm anterior falla si el elemento de datos se repite como {8,8,8,8,8} o {1,8,8 , 8,8} o {8,1,8,8,8} o {8,8,1,8,8} o {8,8,8,8,1}

// solution pasted below will work all test cases :) 

//break the array in two subarray and search for pattern like a[mid]>a[mid+1] 
// and return the min position 

public static int smallestSearch(int[] array,int start,int end) 
{ 
     if(start==end) 
     return array.length; 

     int mid=(start+end)/2; 

     if(array[mid]>array[mid+1]) 
     return min(mid+1,smallestSearch(array,start,mid),smallestSearch(array,mid+1,end)); 
     else 
     return min(smallestSearch(array,start,mid),smallestSearch(array,mid+1,end)); 
} 

public static int min(int a,int b) 
{ 
    if(a==b) 
    return a; 
    else if(a<b) 
     return a; 
     else 
     return b; 
} 
public static int min(int a,int b,int c) 
{ 
    if(a<c) 
    { 
     if(a<b) 
     { 
      return a; 
     } 
     else 
     { 
      return b; 
     } 
    } 
    else 
    { 
     if(b<c) 
     return b; 
     else 
     return c; 
    } 

} 

Answer 3

Mi código está debajo con el algoritmo como comentarios. Funciona incluso para los elementos repetidos.

//Find Min in Rotated Sorted Array 
//Example: int array[10] = {7, 8, 9, 10, 11, 12, 3, 4, 5, 6}; 
// Min in the above array is 3 
// Solution: Recursively search (Modified binary search) for the Pivot where is the smallest Element is present 
// Algorithm: 
// 1) Find the Mid of the Array 
// 2) call the recursive function on segment of array in which there is a deviation in the order 
// If (A[low] > A[mid]) array segment in which deviation in the order present is (low, mid) 
// If (A[low] < A[mid]) array segment in which deviation in the order present is (mid + 1, high) 
// Time Complexity: O(logn) 
// Space Complexity: is of the recursive function stack that is being used 

#define MIN(x,y) (x) <= (y) ? (x): (y) 

int MininRotatedSortedArray(int A[], int low, int high) 
{ 
    if(low > high) 
     return -1; 

    if(low == high - 1) 
     return MIN(A[low], A[high]); 

    int mid = low + (high - low)/2; 

    if(A[low] > A[mid]) 
     return MininRotatedSortedArray(A, low, mid); 
    else if(A[low] < A[mid]) 
     return MininRotatedSortedArray(A, mid + 1, high); 
    else 
     return A[mid]; 
} 

Answer 4

Esto se puede hacer en O (1) mejor de los casos, O (n) tiempo peor de los casos el tiempo, y tiempo O (lg n) en promedio.

Para una matriz ordenada rotada, si el primer elemento de la matriz es menor que el último elemento de la matriz, la matriz ordenada no se gira (o gira 0 posición). El elemento mínimo es simplemente el primer elemento.

Si el elemento medio es menor que el último elemento, entonces el elemento mínimo está en [primero, medio].

Si el elemento medio es mayor que el último elemento, entonces el elemento mínimo está en [centro + 1, último].

Si el elemento medio es igual al último elemento, entonces hay dos subcasos:

1. El primer elemento es más grande que el último elemento, en cuyo caso el elemento mínimo está en [primero, medio + 1];
2. el primer elemento es igual al último elemento, en cuyo caso es no concluyente para rechazar la mitad de la matriz. Reducir a búsqueda lineal. Por ejemplo, para arreglos como [5,5,5,1,5] y [5,1,5,5,5], es imposible simplemente examinando el primer elemento, el último y el medio (ya que todos son iguales) en qué mitad del conjunto se encuentra el elemento mínimo.

Escribí el siguiente código en C++ para resolver este problema, que debería manejar todos los casos (matriz vacía, elementos repetidos).

template <typename Iterator> 
Iterator rotated_min(Iterator begin, Iterator end) 
{ 
    while (begin != end) 
    { 
     if (*begin < *(end - 1)) 
     { 
      return begin; 
     } 
     Iterator mid = begin + (end - 1 - begin)/2; 
     if (*mid < *(end - 1)) 
     { 
      end = mid + 1; 
     } 
     else if (*mid > *(end - 1)) 
     { 
      begin = mid + 1; 
     } 
     else 
     { 
      if (*begin > *(end - 1)) 
      { 
       end = mid + 1; 
       ++begin; 
      } 
      else 
      { 
       //reduce to linear search 
       typename ::std::iterator_traits<Iterator>::value_type min_value = *begin; 
       Iterator min_element = begin; 
       for (Iterator i = begin + 1; i != end; ++i) 
       { 
        if (*i < min_value) 
        { 
         min_value = *i; 
         min_element = i; 
        } 
       } 
       return min_element; 
      } 
     } 
    } 
    return begin; 
} 

Answer 5

Encuentra índice Min en el arreglo ordenado circular

Example : [7,8,9,1,2,3,4,5,6] 

int findMinIndex(int []a, int start, int end) 
{ 
    int mid = (start + end)/2; 

    if (start - end == 1) 
     if(a[start] < a[end]) 
     return start; 
     else 
     return end; 

    if (a[mid] > a[end]){ 

    return findMinIndex(a,mid,end); 

    } 

    else{ 

     return findMinIndex(a,start,mid); 
    } 

    return -1; //Not found 
} 

Answer 6

En caso de que cualquiera lo necesita .. Mi aplicación en Java ..

se encarga de clasificado de forma ascendente/descendente sin clasificar // fin usecases ..

desventaja es que seguirá realizando los pasos log n para encontrar el valor mínimo en un conjunto perfectamente ordenado sin rotación.

http://ideone.com/fork/G3zMIb

/* package whatever; // don't place package name! */ 

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 java.lang.Exception 
    { 
     int [] a = {3,3,0,2,2,2,2,1,2,2,2,2,2,2,2,2,2}; 
     System.out.println(recursiveSplit(a,0,a.length-1)); 
    } 

    public static int findMin(int x, int y){ 
     if(x<=y){ 
      return x; 
     }else{ 
      return y; 
     } 
    } 

    public static int recursiveSplit(int[] arr , int a , int b){ 
     int mid = (int) Math.floor(a + (b-a)/2); 
     int h1_l = a; 
     int h1_u = mid; 
     int h2_l = mid+1; 
     int h2_u = b; 
     int x=0; 
     int y=0; 

     //single element 
     if(a==b){ 
      return arr[a]; 
     } 

     //adjacent positions 
     if(h1_u-h1_l==1){ 
      x=findMin(arr[h1_u],arr[h1_l]); 
     }else{ 
      //else split 
      x=recursiveSplit(arr,h1_l,h1_u); 
     } 

     if(h2_u-h2_l==1){ 
      y=findMin(arr[h2_u],arr[h2_l]); 
     }else{ 
      y=recursiveSplit(arr, h2_l,h2_u); 
     } 

     return findMin(x, y); 
    } 
} 

errores/sugerencias/fallidos casos de uso son bienvenidos

Answer 7

public int findMin(int[] num) { 
     return findMin(num, 0, num.length-1); 
    } 
    public int findMin(int[] num, int left, int right){ 
     if(left==right) return num[left]; 
     if(left+1==right) return Math.min(num[left], num[right]); 
     int mid = (left+right)/2; 
     if(num[mid]>num[right]){ 
      return findMin(num,mid+1,right); 
     }else if(num[mid]<num[right]){ 
      return findMin(num,left,mid); 
     }else{ 
      if(num[mid]==num[left]){ 
       return Math.min(findMin(num,left,mid), findMin(num,mid,right)); 
      }else{ 
       return findMin(num,left,mid); 
      } 
     } 
    } 

Answer 8

El siguiente algoritmo toma tiempo log (n). Suponiendo que la matriz no tiene duplicados.

public int findMin(int[] num) { 
    if(num.length == 0) return -1 
    int r = num.length-1, l = 0; 
    while(l<r){ 
     if(num[l]<=num[r]) return num[l]; //when not rotated, return the left most value 
     int mid = (r+l)/2; 
     if(num[mid]<num[r]){ 
      r = mid; 
     }else{ 
      l = mid+1; 
     } 
    } 
    return num[l]; 
} 

Answer 9

Lo hice usando una versión ligeramente modificada de la búsqueda binaria. Lo que estoy haciendo aquí es seguir hacia la izquierda o hacia la derecha en función de dónde podría estar el mínimo. Por ejemplo, en una matriz ascendente si el elemento medio es menor que el elemento más a la izquierda, es posible que el mínimo esté a la izquierda. Mientras vuelvo a recorrer la matriz, también hago un seguimiento del mínimo. La recursión continúa hasta el final y luego se devuelve el último mínimo. Esto también funciona con elementos repetidos.

public static void main(String[] args) throws IOException { 

    int[] rotated = {6, 7, 8, 1, 2, 3, 4, 5}; 
    int min = findMin(rotated); 
    System.out.println(min);//1 


} 

public static int findMin(int[] sorted) { 
    return findMinRecursively(sorted, sorted[0], 0, (sorted.length - 1)); 
} 


private static int findMinRecursively(int[] sorted, int min, int leftIndex, int rightIndex) { 

    if (leftIndex > rightIndex) { 
     return min; 
    } 

    int midIndex = (leftIndex + rightIndex)/2; 
    if (sorted[midIndex] < min) { 
     min = sorted[midIndex]; 
    } 

    if (sorted[midIndex] < sorted[leftIndex]) { 
     return findMinRecursively(sorted, min, leftIndex, (midIndex - 1)); 
    } else { 
     return findMinRecursively(sorted, min, (midIndex + 1), rightIndex); 
    } 
}