Algorithme efficace pour: Étant donné un tableau non trié d'entiers positifs et un entier N, renvoyer N si N existait dans le tableau ou le premier nombre & lt; N

J'ai eu cette question:

Donné un tableau non-trié des nombres entiers positifs et un entier N, retour N si N existait dans le tableau ou le premier nombre est plus petit que N.

dans une interview et je voulais savoir quel serait le meilleur algorithme efficace pour le résoudre?

J'avais donné deux approches à l'aide de hachage et de tri de tableau, mais ce n'était pas correct et efficace. Je serais vraiment reconnaissant si quelqu'un peut donner un algorithme optimal pour ce problème.

source d'informationauteur Rachel

  1. 16

    Je suppose que c'est dans un style C langue; si non, veuillez mettre à jour la question afin de refléter la langue.

    Si le tableau n'est pas trié, alors vous n'avez pas le choix, mais un (potentiellement) une traversée complète de la matrice de chercher Ncomme toute opération de tri va prendre plus de temps que de simplement traverser le tableau (autres que par recherche de l'élément par "chance"). Quelque chose de semblable à ce serait probablement le plus efficace (sauf si je suis absent quelque chose)

    int retVal = -1;

for(int i = 0; i < ARRAY_LENGTH; i++)
{
    if(array[i] == N) return N;
    if(retVal == -1 && array[i] < N) retVal = array[i];
}

return retVal;

    Comme le suggère d'ailleurs, vous pouvez modifier

    if(retVal == -1 && array[i] < N) retVal = array[i];

    à

    if(retVal < array[i] && array[i] < N) retVal = array[i];

    Afin d'obtenir la plus grande valeur inférieure à Nplutôt que de simplement la première.

  2. 13

    Parcourir la liste du début à la fin, si vous voyez une valeur inférieure à N, tenez le premier jusqu'à ce que vous atteignez la fin, ou trouver N. Si vous trouvez N, le retourner, si vous arrivez à la fin, le retour de la valeur que vous avez retenu. Sans doute il faudrait être certain de la valeur à renvoyer si toutes les valeurs ont été plus grande que N, mais le problème n'est pas l'état qui.

    O(N) de la performance, O(1) utilisation de l'espace.

    Il est un peu plus compliqué si vous êtes à la recherche de la plus grande valeur inférieure à N. Dans ce cas, au lieu de s'en tenir à la première valeur inférieure à N, il vous suffit de saisir une nouvelle valeur à chaque fois que vous trouver une valeur inférieure à N, mais plus grand que la valeur que vous êtes en possession d'.

    Il suffit de remplacer 

    if(array[i] < N && retVal == -1) retVal = array[i];

    avec

    if(array[i] < N && retVal < array[i]) retVal = array[i];

    dans Adam répondre

  3. 0

    Voici mon code:

    int getNindex(int a[],int n,int N)
{
    int min=-99999,i=0,minindex=-1;
    for(i=0;i<n;i++)
    {
        if(a[i]>min && a[i]<=N)
        {
            min=a[i];
            minindex=i;
        }
    }
    return minindex;
}

int main()
{
    int a[]={5,75,20,50,100};
    int Nindex=getNindex(a,5,60);
    if(Nindex>=0)
        printf("index= %d,N= %d\n",Nindex,a[Nindex]);
    return 0;
}