Signification de deux comparaisons lorsqu'on parle de tableaux

Question

C'est la question exacte du site web.

Soit un tableau trié de 10 éléments qui contient 6 nombres différents, dont un seul est répété cinq fois. Votre tâche consiste à trouver le numéro en double en utilisant deux comparaisons seulement.

Je ne suis pas sûr de ce que signifie "deux comparaisons" ici. Pourriez-vous m'éclairer à ce sujet ? Merci.

Voici mon code en réponse à cette question.

using namespace std;

int FindDuplicate(vector<int>& nums)
{

int count = 1, marked = 0;

for (int i = 0; i < nums.size(); i++)
{       

    if (nums[i + 1] == nums[marked])
    {
        count++;

        if (count == 5)
            return nums[marked];
    }

    else
    {
        marked = i + 1;
        count = 1;
    }
}

return 0;
}

Answer 1

Ici 2 comparaisons signifie que vous n'effectuez que 2 opérations primitives de comparaisons.

if(a > b) peut être considéré comme 1 comparaison. Mais

if(a > b && c < d) est considéré comme 2 comparaisons.

if(a > b) lorsqu'il est exécuté 2 fois est aussi 2 comparaisons.

Maintenant que le tableau est trié et il n'y a que 6 éléments distincts :

Nous pouvons facilement énumérer les différentes possibilités d'éléments de tableau et arriver à la conclusion que :

L'élément à indice 5 quand il est égal à :

Élément à indice 6 la réponse dans ce cas est élément à l'indice 6

Sinon,

El élément à l'indice 4 est la réponse.

Ainsi, le solution est :

if(array[5] == array[6])
 return array[5];
else return array[4];

Answer 2

"Deux comparaisons" signifie que vous ne pouvez comparer que deux fois. Par exemple, une solution légale avec deux comparaisons serait :

• Comparer le premier nombre avec le second (première comparaison)
  • Si le premier est plus grand que le second, comparez le premier au troisième (deuxième comparaison).
    • Si le premier est encore plus grand, le premier est la solution (pas de comparaison).
    • Si le premier n'est pas plus grand, le troisième est la solution (sans comparaison).
  • Si le premier n'est pas plus grand que le second, comparez le second au quatrième (deuxième comparaison).

etc...

Notez que c'est probablement pas la solution à la question posée, juste un exemple de ce que signifie "deux comparaisons".

Answer 3

Les comparaisons sont des opérations comme == o < . "Deux comparaisons" signifie que votre programme n'est autorisé à faire ce genre de chose que deux fois pour les nombres du tableau.

Sans cette restriction, vous pourriez simplement parcourir le tableau en boucle et comparer chaque nombre à celui qui le précède. Cette méthode permettrait de trouver le numéro en double, mais elle pourrait nécessiter un grand nombre de comparaisons si le numéro en double se trouve à la fin du tableau. Limiter l'algorithme à deux comparaisons signifie que vous devez trouver quelque chose de plus astucieux.

Answer 4

La comparaison à deux signifie que la comparaison globale doit être à deux seulement lorsque vous obtenez la réponse. Le programme que vous avez écrit fait des comparaisons multiples parce que pour chaque itération de la boucle vous faites deux comparaisons (une dans for, et l'autre dans if) et dans le pire des cas cette boucle itérera pendant 10 fois, c'est-à-dire la taille de votre tableau.

L'élément dupliqué peut être facilement obtenu en une seule comparaison si vous regardez le modèle ici.Supposons que les six numéros différents sont de 1 à 6. Essayons maintenant de faire en sorte que chaque élément se répète 5 fois, nous obtiendrons alors

    1 repeating => 1 1 1 1 1 2 3 4 5 6
    2 repeating => 1 2 2 2 2 2 3 4 5 6
    3 repeating => 1 2 3 3 3 3 3 4 5 6
    4 repeating => 1 2 3 4 4 4 4 4 5 6
    5 repeating => 1 2 3 4 5 5 5 5 5 6
    6 repeating => 1 2 3 4 5 6 6 6 6 6

Dans les cas ci-dessus, si vous analysez, à part le dernier cas, nums[4] (indexation à partir de 0) est toujours un élément répétitif. Donc tout ce que vous devez faire est

if(nums[5] == nums[6])
   return nums[5];
else 
   return nums[4]

Answer 5

Deux comparaisons signifie tous les cas où des valeurs sont comparées, donc vous ne pouvez pas utiliser la boucle for.

Pour résoudre cette énigme, notez qu'il n'y a en fait que 6 entrées de données possibles qui ne sont pas trivialement équivalentes :

1: 0 0 0 0 0 1 2 3 4 5
2: 0 1 1 1 1 1 2 3 4 5
3: 0 1 2 2 2 2 2 3 4 5
4: 0 1 2 3 3 3 3 3 4 5
5: 0 1 2 3 4 4 4 4 4 5
6: 0 1 2 3 4 5 5 5 5 5

La question est donc de savoir comment l'utiliser de manière optimale. Si vous comparez les chiffres du milieu et qu'ils sont égaux, vous pouvez répondre immédiatement aux cas 2 à 5. La deuxième comparaison permet de distinguer les cas 1 et 6. Le problème est donc assez simple :

if (tab[4] == tab[5])
    return tab[4];
else if (tab[0] == tab[1))
    return tab[0];
else
    return tab[9];