c++ - tabla - Buscando en una matriz ordenada y rotada

matrices en c++

Question

Mientras me preparaba para la entrevista técnica, me encontré con esta interesante pregunta:

Te han dado una matriz que se ordena y luego gira.

ejemplo

Deje arr = [1,2,3,4,5] que se clasifica y luego se gira, diga dos veces a la derecha para dar

[4,5,1,2,3]

Ahora, ¿qué mejor puede uno buscar en esta matriz ordenada + girada?

Uno puede deshacer la matriz y luego hacer una búsqueda binaria. Pero no es mejor que hacer una búsqueda lineal en la matriz de entrada ya que ambas son el peor caso O (N).

Por favor, brinde algunos consejos. He buscado mucho en algoritmos especiales para esto, pero no he podido encontrar ninguno.

Entiendo c y c ++

Answer 1

Aquí hay una solución simple (tiempo, espacio) eficiente no recursiva de O (log n) python que no modifica la matriz original. Corta la matriz rotada por la mitad hasta que solo tenga dos índices para verificar y devuelve la respuesta correcta si coincide un índice.

def findInRotatedArray(array, num):

lo,hi = 0, len(array)-1
ix = None


while True:


    if hi - lo <= 1:#Im down to two indices to check by now
        if (array[hi] == num):  ix = hi
        elif (array[lo] == num): ix = lo
        else: ix = None
        break

    mid = lo + (hi - lo)/2
    print lo, mid, hi

    #If top half is sorted and number is in between
    if array[hi] >= array[mid] and num >= array[mid] and num <= array[hi]:
        lo = mid

    #If bottom half is sorted and number is in between
    elif array[mid] >= array[lo] and num >= array[lo] and num <= array[mid]:
        hi = mid


    #If top half is rotated I know I need to keep cutting the array down
    elif array[hi] <= array[mid]:
        lo = mid

    #If bottom half is rotated I know I need to keep cutting down
    elif array[mid] <= array[lo]:
        hi = mid

print "Index", ix

Answer 2

Esto se puede hacer en O(logN) usando una búsqueda binaria ligeramente modificada.

La propiedad interesante de una matriz ordenada + girada es que cuando la divide en dos mitades, al menos una de las dos mitades siempre se ordenará.

Let input array arr = [4,5,6,7,8,9,1,2,3]
number of elements  = 9
mid index = (0+8)/2 = 4

[4,5,6,7,8,9,1,2,3]
         ^
 left   mid  right

como parece correcto, la sub-matriz no está ordenada mientras que la sub-matriz izquierda está ordenada.

Si el medio es el punto de rotación, se ordenarán las sub-matrices izquierda y derecha.

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

Pero en cualquier caso, una mitad (sub-matriz) debe ser ordenada .

Podemos saber fácilmente qué mitad se ordena comparando los elementos de inicio y fin de cada mitad.

Una vez que encontremos qué mitad está ordenada, podemos ver si la clave está presente en esa comparación medio simple con los extremos.

Si la clave está presente en esa mitad, llamamos recursivamente a la función en esa mitad
de lo contrario, recursivamente llamamos a nuestra búsqueda en la otra mitad.

Estamos descartando la mitad de la matriz en cada llamada que hace que este algoritmo sea O(logN) .

Pseudo código:

function search( arr[], key, low, high)

        mid = (low + high) / 2

        // key not present
        if(low > high)
                return -1

        // key found
        if(arr[mid] == key)
                return mid

        // if left half is sorted.
        if(arr[low] <= arr[mid]) {

                // if key is present in left half.
                if (arr[low] <= key && arr[mid] >= key) 
                        return search(arr,key,low,mid-1)

                // if key is not present in left hald..search right half.
                else                 
                        return search(arr,key,mid+1,high)
                end-if

        // if righ half is sorted. 
        else    
                // if key is present in right half.
                if(arr[mid] <= key && arr[high] >= key) 
                        return search(arr,key,mid+1,high)

                // if key is not present in right half..search in left half.
                else
                        return search(arr,key,low,mid-1)
                end-if
        end-if  

end-function

La clave aquí es que una sub-matriz siempre será ordenada, con lo que podemos descartar la mitad de la matriz.

Answer 3

La respuesta seleccionada tiene un error cuando hay elementos duplicados en la matriz. Por ejemplo, arr = {2,3,2,2,2} y 3 es lo que estamos buscando. Luego, el programa en la respuesta seleccionada devolverá -1 en lugar de 1.

Esta pregunta de la entrevista se trata en detalle en el libro "Cracking the Coding Interview". La condición de los elementos duplicados se discute especialmente en ese libro. Como la OP dijo en un comentario que los elementos de la matriz pueden ser cualquier cosa, estoy dando mi solución como pseudo código a continuación:

function search( arr[], key, low, high)

    if(low > high)
        return -1

    mid = (low + high) / 2

    if(arr[mid] == key)
        return mid

    // if the left half is sorted.
    if(arr[low] < arr[mid]) {

        // if key is in the left half
        if (arr[low] <= key && key <= arr[mid]) 
            // search the left half
            return search(arr,key,low,mid-1)
        else
            // search the right half                 
            return search(arr,key,mid+1,high)
        end-if

    // if the right half is sorted. 
    else if(arr[mid] < arr[low])    
        // if the key is in the right half.
        if(arr[mid] <= key && arr[high] >= key) 
            return search(arr,key,mid+1,high)
        else
            return search(arr,key,low,mid-1)
        end-if

    else if(arr[mid] == arr[low])

        if(arr[mid] != arr[high])
            // Then elements in left half must be identical. 
            // Because if not, then it''s impossible to have either arr[mid] < arr[high] or arr[mid] > arr[high]
            // Then we only need to search the right half.
            return search(arr, mid+1, high, key)
        else 
            // arr[low] = arr[mid] = arr[high], we have to search both halves.
            result = search(arr, low, mid-1, key)
            if(result == -1)
                return search(arr, mid+1, high, key)
            else
                return result
   end-if
end-function

Answer 4

Mi código simple: -

public int search(int[] nums, int target) {
    int l = 0;
    int r = nums.length-1;
    while(l<=r){
        int mid = (l+r)>>1;
        if(nums[mid]==target){
            return mid;
        }
        if(nums[mid]> nums[r]){
            if(target > nums[mid] || nums[r]>= target)l = mid+1;
            else r = mid-1;
        }
        else{
            if(target <= nums[r] && target > nums[mid]) l = mid+1;
            else r = mid -1;
        }
    }
    return -1;
}

Complejidad de tiempo O (log (N)).

Answer 5

Mi primer intento sería encontrar usando la búsqueda binaria el número de rotaciones aplicadas; esto se puede hacer buscando el índice n donde a [n]> a [n + 1] usa el mecanismo de búsqueda binario habitual. Luego haga una búsqueda binaria regular mientras gira todos los índices por turno encontrado.

Answer 6

Otro enfoque que funcionaría con valores repetidos es encontrar la rotación y luego hacer una búsqueda binaria regular aplicando la rotación cada vez que accedemos a la matriz.

test = [3, 4, 5, 1, 2]
test1 = [2, 3, 2, 2, 2]

def find_rotated(col, num):
    pivot = find_pivot(col)
    return bin_search(col, 0, len(col), pivot, num)

def find_pivot(col):
    prev = col[-1]
    for n, curr in enumerate(col):
        if prev > curr:
            return n
        prev = curr
    raise Exception("Col does not seem like rotated array")

def rotate_index(col, pivot, position):
    return (pivot + position) % len(col)

def bin_search(col, low, high, pivot, num):
    if low > high:
        return None
    mid = (low + high) / 2
    rotated_mid = rotate_index(col, pivot, mid)
    val = col[rotated_mid]
    if (val == num):
        return rotated_mid
    elif (num > val):
        return bin_search(col, mid + 1, high, pivot, num)
    else:
        return bin_search(col, low, mid - 1,  pivot, num)

print(find_rotated(test, 2))
print(find_rotated(test, 4))
print(find_rotated(test1, 3))

Answer 7

Para una matriz girada con duplicados, si uno necesita encontrar la primera aparición de un elemento, se puede usar el siguiente procedimiento (código Java):

public int mBinarySearch(int[] array, int low, int high, int key)
{
    if (low > high)
        return -1; //key not present

    int mid = (low + high)/2;

    if (array[mid] == key)
        if (mid > 0 && array[mid-1] != key)
            return mid;

    if (array[low] <= array[mid]) //left half is sorted
    {
        if (array[low] <= key && array[mid] >= key)
            return mBinarySearch(array, low, mid-1, key);
        else //search right half
            return mBinarySearch(array, mid+1, high, key);
    }
    else //right half is sorted
    {
        if (array[mid] <= key && array[high] >= key)
            return mBinarySearch(array, mid+1, high, key);
        else
            return mBinarySearch(array, low, mid-1, key);
    }       

}

Esto es una mejora al procedimiento de coadicto de arriba. Observe la condición adicional si, como a continuación:

if (mid > 0 && array[mid-1] != key)

Answer 8

Primero, necesitas encontrar la constante de cambio, k. Esto se puede hacer en el tiempo O (lgN). A partir del cambio constante k, puede encontrar fácilmente el elemento que está buscando utilizando una búsqueda binaria con la constante k. La búsqueda binaria aumentada también toma el tiempo O (lgN). El tiempo total de ejecución es O (lgN + lgN) = O (lgN)

Para encontrar el cambio constante, k. Solo tienes que buscar el valor mínimo en la matriz. El índice del valor mínimo de la matriz le indica el cambio constante. Considere la matriz ordenada [1,2,3,4,5].

The possible shifts are: [1,2,3,4,5] // k = 0 [5,1,2,3,4] // k = 1 [4,5,1,2,3] // k = 2 [3,4,5,1,2] // k = 3 [2,3,4,5,1] // k = 4 [1,2,3,4,5] // k = 5%5 = 0

Para hacer cualquier algoritmo en tiempo O (lgN), la clave es encontrar siempre formas de dividir el problema a la mitad. Una vez hecho esto, el resto de los detalles de implementación es fácil

A continuación se muestra el código en C ++ para el algoritmo

// This implementation takes O(logN) time
// This function returns the amount of shift of the sorted array, which is
// equivalent to the index of the minimum element of the shifted sorted array. 
#include <vector> 
#include <iostream> 
using namespace std; 

int binarySearchFindK(vector<int>& nums, int begin, int end)
{
    int mid = ((end + begin)/2); 
    // Base cases
    if((mid > begin && nums[mid] < nums[mid-1]) || (mid == begin && nums[mid] <= nums[end]))     
        return mid; 
    // General case 
    if (nums[mid] > nums[end]) 
    {
        begin = mid+1; 
        return binarySearchFindK(nums, begin, end); 
    }
    else
    {
        end = mid -1; 
        return binarySearchFindK(nums, begin, end); 
    }   
}  
int getPivot(vector<int>& nums)
{
    if( nums.size() == 0) return -1; 
    int result = binarySearchFindK(nums, 0, nums.size()-1); 
    return result; 
}

// Once you execute the above, you will know the shift k, 
// you can easily search for the element you need implementing the bottom 

int binarySearchSearch(vector<int>& nums, int begin, int end, int target, int pivot)
{
    if (begin > end) return -1; 
    int mid = (begin+end)/2;
    int n = nums.size();  
    if (n <= 0) return -1; 

    while(begin <= end)
    {
        mid = (begin+end)/2; 
        int midFix = (mid+pivot) % n; 
        if(nums[midFix] == target) 
        {
            return midFix; 
        }
        else if (nums[midFix] < target)
        {
            begin = mid+1; 
        }
        else
        {
            end = mid - 1; 
        }
    }
    return -1; 
}
int search(vector<int>& nums, int target) {
    int pivot = getPivot(nums); 
    int begin = 0; 
    int end = nums.size() - 1; 
    int result = binarySearchSearch(nums, begin, end, target, pivot); 
    return result; 
}

Hope this helps!=) Soon Chee Loong, University of Toronto

Answer 9

Prueba esta solución

bool search(int *a, int length, int key)
{
int pivot( length / 2 ), lewy(0), prawy(length);
if (key > a[length - 1] || key < a[0]) return false;
while (lewy <= prawy){
    if (key == a[pivot]) return true;
    if (key > a[pivot]){
        lewy = pivot;
        pivot += (prawy - lewy) / 2 ? (prawy - lewy) / 2:1;}
    else{
        prawy = pivot;
        pivot -= (prawy - lewy) / 2 ? (prawy - lewy) / 2:1;}}
return false;
}

Answer 10

Puedes hacer 2 búsquedas binarias: primero para encontrar el índice i tal que arr[i] > arr[i+1] .

Aparentemente, (arr/[1], arr[2], ..., arr[i]) y (arr[i+1], arr[i+2], ..., arr[n]) son ambos arreglos ordenados

Entonces, si arr[1] <= x <= arr[i] , se realiza una búsqueda binaria en la primera matriz, en otro caso en la segunda.

La complejidad O(logN)

EDITAR: el código .

Answer 11

Respuesta para la publicación mencionada anteriormente "Esta pregunta de la entrevista se trata en detalle en el libro ''Cracking the Coding Interview''. La condición de los elementos duplicados se discute especialmente en ese libro. Como la OP dijo en un comentario que los elementos de la matriz pueden ser cualquier cosa, estoy dando mi solución como pseudo código en la siguiente página:

Tu solución es O (n) !! (La última condición if donde se verifican ambas mitades de la matriz para una sola condición lo convierte en un sol de complejidad de tiempo lineal)

Es mejor hacer una búsqueda lineal que quedar atrapado en un laberinto de errores y fallas de segmentación durante una ronda de codificación.

No creo que haya una mejor solución que O (n) para una búsqueda en una matriz ordenada rotativa (con duplicados)

Answer 12

Si sabe cómo (hasta ahora) se giró, aún puede hacer una búsqueda binaria.

El truco es que obtienes dos niveles de índices: haces los bs en un rango virtual 0..n-1 y luego los giras al buscar un valor.

Answer 13

Si sabe que la matriz se ha girado a la derecha, simplemente puede hacer una búsqueda binaria desplazada a la derecha. Esto es O (lg N)

Con esto, quiero decir, inicializar el límite izquierdo para s y el derecho a (s-1) mod N, y hacer una búsqueda binaria entre estos, teniendo un poco de cuidado para trabajar en el área correcta.

Si no sabe por cuánto ha girado la matriz, puede determinar qué tan grande es la rotación utilizando una búsqueda binaria, que es O (lg N), luego realice una búsqueda binaria desplazada, O (lg N), una gran total de O (lg N) aún.

Answer 14

no es necesario rotar la matriz primero, puede usar la búsqueda binaria en la matriz girada (con algunas modificaciones)

supongamos que N es el número que busca:

lea el primer número (arr [inicio]) y el número en el medio de la matriz (arr [end]):

• si arr [inicio]> arr [fin] -> la primera mitad no está ordenada, pero la segunda mitad está ordenada:

  • if arr [end]> N -> el número está en índice: (middle + N - arr [end])

  • si N repite la búsqueda en la primera parte de la matriz (vea el extremo para estar en el medio de la primera mitad de la matriz, etc.)

(Lo mismo si la primera parte está ordenada pero la segunda no)

Answer 15

int rotated_binary_search(int A[], int N, int key) {
  int L = 0;
  int R = N - 1;

  while (L <= R) {
    // Avoid overflow, same as M=(L+R)/2
    int M = L + ((R - L) / 2);
    if (A[M] == key) return M;

    // the bottom half is sorted
    if (A[L] <= A[M]) {
      if (A[L] <= key && key < A[M])
        R = M - 1;
      else
        L = M + 1;
    }
    // the upper half is sorted
    else {
      if (A[M] < key && key <= A[R])
        L = M + 1;
      else
        R = M - 1;
    }
  }
  return -1;
}

Answer 16

public class PivotedArray {

//56784321 first increasing than decreasing
public static void main(String[] args) {
    // TODO Auto-generated method stub
    int [] data ={5,6,7,8,4,3,2,1,0,-1,-2};

    System.out.println(findNumber(data, 0, data.length-1,-2));

}

static int findNumber(int data[], int start, int end,int numberToFind){

    if(data[start] == numberToFind){
        return start;
    }

    if(data[end] == numberToFind){
        return end;
    }
    int mid = (start+end)/2;
    if(data[mid] == numberToFind){
        return mid;
    }
    int idx = -1;
    int midData = data[mid];
    if(numberToFind < midData){
        if(midData > data[mid+1]){
            idx=findNumber(data, mid+1, end, numberToFind);
        }else{
            idx =  findNumber(data, start, mid-1, numberToFind);
        }
    }

    if(numberToFind > midData){
        if(midData > data[mid+1]){
            idx =  findNumber(data, start, mid-1, numberToFind);

        }else{
            idx=findNumber(data, mid+1, end, numberToFind);
        }
    }
    return idx;
}

}

Answer 17

short mod_binary_search( int m, int *arr, short start, short end)
{

 if(start <= end)
 {
    short mid = (start+end)/2;

    if( m == arr[mid])
        return mid;
    else
    {
        //First half is sorted
        if(arr[start] <= arr[mid])
        {
            if(m < arr[mid] && m >= arr[start])
                return mod_binary_search( m, arr, start, mid-1);
            return mod_binary_search( m, arr, mid+1, end);
        }

        //Second half is sorted
        else
        {
            if(m > arr[mid] && m < arr[start])
                return mod_binary_search( m, arr, mid+1, end);
            return mod_binary_search( m, arr, start, mid-1);
        }
    }
 }
 return -1;
}