Trouver le plus petit nombre dans la matrice rotative triée

Je suis tombé sur cette question dans une Interview. S'il vous plaît aidez-moi à obtenir la solution.

Question est:

Vous avez trié rotatif tableau, j'. e. le tableau contient des éléments qui sont triés et il peut être tourné de manière circulaire, comme si les éléments du tableau sont [5,6,10,19,20,29], puis en faisant tourner première fois tableau devient [29,5,6,10,19,20] et en deuxième temps, il devient [20,29,5,6,10,19] et ainsi de suite.

Si vous avez besoin de trouver le plus petit élément du tableau à tout moment. Vous ne serez pas fourni avec le nombre de fois de la matrice de rotation. Juste compte tenu de la rotation des éléments d'un tableau et de trouver le plus petit d'entre eux. Dans ce cas, la sortie devrait être de 5.

source d'informationauteur Mojoy

algorithm

35

Méthode 1:

Vous pouvez le faire dans O(logN) temps.

Utiliser une version modifiée de recherche binaire pour trouver le point de rotation qui est un indice i tels que
arr[i] > arr[i+1].

Exemple:
```
[6,7,8,9,1,2,3,4,5]
       ^
       i
```
Les deux sous-tableaux
(arr[1], arr[2], .., arr[i]) et
(arr[i+1], arr[i+2], ..., arr[n]) sont triés.

La réponse est min(arr[1], arr[i+1])

Méthode 2:

Lorsque vous divisez le tri, la rotation de tableau en deux moitiés (arr[1],..,arr[mid]) et (arr[mid+1],..,arr[n])l'un d'eux est toujours triée et l'autre toujours a la min. Nous pouvons directement utiliser une version modifiée de recherche binaire de continuer à chercher dans les ménagères de la moitié
```
//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]
```

Ci-dessus algorihtm échoue si l'élément de données est répété comme {8,8,8,8,8} ou {1,8,8,8,8} ou {8,1,8,8,8} ou {8,8,1,8,8} ou {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;
    }

}

De Trouver le plus petit nombre dans la triés rotation de tableau:
à l'aide de la recherche Binaire concept

public class RotatedSortedArrayWithoutDuplicates1 {

    public static void main(String[] args) {
        int[] a = { 4, 6, 8, 10, 34, 56, 78, 1, 3 };

        System.out.println(findMin(a));

    }

    private static int findMin(int[] a) {
        if (a.length == 0 || a == null) {
            return -1;
        }
        int start = 0;
        int last = a.length - 1;
        while (start + 1 < last) {
            int mid = start + (last - start) /2;
            int m = a[mid];
            int s = a[start];
            int l = a[last];

            if (m > l) {
                start = mid + 1;
            }
            if (m < l) {
                last = mid;
            } else {
                last--;
            }

        } //while

        if (a[start] > a[last]) {
            return a[last];
        } else {
            return a[start];
        }

    }
}

Mais si vous ne voulez pas utiliser les Binaires de Recherche, puis :

public class Abc {
    public static void main(String[] args) {
        int[] a = { 4, 5, 6, 7, 7, 8, 9, 1, 1, 2, 3, 3 };
        System.out.println(findMin(a));
    }

    public static int findMin(int[] a) {

        int min = a[a.length - 1];

        for (int i = 0; i < a.length; i++) {
            if (min > a[i]) {
                min = a[i];
                break;
            }
        }
        return min;

    }//findmin
}//end

Voici le code en Python:

def fix(a):
    min = a[0]
    for i in range(len(a)):
        if(min > a[i]):
            min = a[i]
            break

    return min        


a = [2, 2,3,4,1,2]
print(fix(a))

Mon code est ci-dessous avec l'algorithme sous forme de commentaires. Fonctionne même pour les éléments répétés.

//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];
}

0

Cela peut être fait en O(1) fois dans le meilleur des cas, en O(n) fois pire des cas, et O(lg n) de temps en moyenne.

Pour une rotation du tableau trié, si le premier élément du tableau est moins que le dernier élément dans le tableau, puis le tableau trié est pas tourné (ou rotation vers la position 0). L'élément minimum est tout simplement le premier élément.

Si le milieu de l'élément est moins que le dernier élément, alors le minimum de l'élément est dans le [premier, milieu].

Si le milieu de l'élément est plus grand que le dernier élément, alors le minimum de l'élément est dans [milieu + 1, dernier].

Si le milieu de l'élément est égal au dernier élément, alors il y a deux sous-cas:
1. le premier élément est plus grand que le dernier élément, auquel cas l'élément minimum est en premier, milieu + 1];
2. le premier élément est égal au dernier élément, auquel cas il est pas concluants de rejeter une ou l'autre moitié du tableau. Réduire à la recherche linéaire. Par exemple, pour des tableaux tels que [5,5,5,1,5] et [5,1,5,5,5], il est impossible par examiner la première, la dernière et le moyen de l'élément (puisqu'ils sont tous égaux) dont la moitié de la matrice de l'élément minimum de mensonges.
J'ai écrit le code suivant en C++ pour résoudre ce problème, qui doit gérer tous les cas (tableau vide, les éléments répétés).
```
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;
}
```

Trouver Min index dans la circulaire tableau trié

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
}

Dans le cas où on a besoin d'elle.. Mon implémentation en java..

prend soin de trier/non triés dans l'ordre croissant//ordre décroissant usecases..

inconvénient est qu'il sera toujours effectuer log n étapes pour trouver la valeur min dans un parfait ensemble trié, sans rotation.

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);
    }
}

Erreurs/suggestions/l'échec de la usecases sont accueillis

    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);
            }
        }
    }

L'algorithme suivant prend log(n) fois. En supposant que le tableau n'a pas de doublon.

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];
}

Je l'ai fait à l'aide d'une version légèrement modifiée de recherche binaire. Ce que je fais ici est je continue à gauche ou à droite selon l'endroit où le minimum pourrait être. Par exemple dans un croissant tableau si le milieu de l'élément est inférieur gauche de la plupart élément, il est possible que le minimum est à gauche. Alors que recursing à travers le tableau, j'ai aussi garder une trace de la minimale. La récursivité se poursuit jusqu'à la fin et puis la dernière minute est retourné. Cela fonctionne également avec les éléments répétés.

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);
    }
}

Question : Trouver le minimum triés rotation de tableau .
Solution 1 : Utilisation De La Recherche Binaire

class Test18 {
    public static void main(String[] args) {
        int[] a = { 5, 6, 7, 8, 9, 10, 1, 2, 3 };

        System.out.println(findmin(a));

    }

    //find min in a sorted rotated array
    private static int findmin(int[] a) {
        int start = 0;
        int last = a.length - 1;
        while (start + 1 < last) {
            int mid = start + (last - start) /2;
            if (a[mid] > a[last]) {
                start = mid + 1;
            }
            if (a[mid] < a[last]) {
                last = mid;
            } else {
                mid--;
            }

        } //while
        if (a[start] > a[last]) {
            return a[last];
        } else {
            return a[start];
        }

    }
}

Vous devez vous connecter pour publier un commentaire.