Algorithmes de tableau

Question

J'ai une question à poser sur les algorithmes. On m'a demandé d'écrire l'algorithme sur ceci: Ne pas vous demander d'écrire l'algo pour moi, mais faites-moi savoir le processus efficace ce que je dois faire:

Il y a un tableau de n éléments comme le livre ou contenu de la Bible, et Supposons que vous avez inséré une chaîne d'entrée "Gaurav Agarwal" dans cela. Ce que vous voulez faire, vous devez récupérer les éléments uniques qui sont présents dans le tableau pour cette chaîne. Juste un algorithme comment vous allez aller plus loin (non triés)

Si vous n'avez pas compris alors faites le moi savoir et je vais essayer de vous aider à ce sujet.

Answer 1

Une bonne façon de trouver des doublons dans un tableau non trié est de faire le tri sur la base des éléments de chaîne, donc l'algorithme de votre devoirs question serait:

1. Trier le tableau
2. vérifiez votre tableau pour l'existence de "Gaurav Agarwal". Comme il est trié, les éléments voisins seraient la même chaîne, et ce que vous devez faire est alors de garder un compteur et de l'incrémenter jusqu'à ce que vous trouviez le premier élément de tableau qui n'est pas égal à la chaîne que vous recherchez

Answer 2

Je ne pense pas que le tri et la recherche soient la solution la plus efficace à votre problème.

Le tri lui-même a une complexité nlogn.

Il suffit de faire une recherche bruteforce de tableau est plus efficace (a une complexité de n)

Tel est le cas si vous trouvez des éléments uniques pour une chaîne ou quelques chaînes. Si vous essayez de trouver des éléments uniques pour un grand nombre de chaînes d'entrée au lieu d'une seule, le tri est logique.

Answer 3

Il faudra un certain temps pour trier le tableau de chaînes, puis pour l'analyser. Je recommande simplement d'analyser le tableau de chaîne et de vérifier si la longueur de votre chaîne est la même que la longueur de la chaîne à partir de la position actuelle du tableau. Si la longueur est la même, comparez les 2 chaînes

Answer 4

Je procéderais dans les étapes suivantes:

1. J'utiliser une table de hachage avec chaînage, en utilisant une fonction de hachage qui fonctionne bien pour les chaînes.
2. trouver le hachage de la nouvelle chaîne et rechercher la liste chaînée de l'emplacement correspondant à ce hachage pour les doublons.