Comment écrire une implémentation pour une fonction qui prend en entrée une séquence de caractères ASCII et qui donne le symbole le plus fréquemment récurrent? J’ai besoin de le faire sur C, où est ma mauvaise?
char mostFrequentCharacter(char* str, int size); char value; int valueCount = 0; for (int i =0; i = valueCount) { valueCount = totalCount; value = oneChar; } } return value;
La fonction doit être optimisée pour fonctionner sur un périphérique doté de processeurs à double cœur basés sur ARM et d’une quantité de mémoire infinie.
Si la mémoire n’est pas un problème comme vous l’avez noté, vous devez créer une table de consultation dans laquelle vous stockerez le nombre d’occurrences pour chaque caractère. Etant donné que l’entrée est une séquence de caractères ASCII, la taille de la structure doit être de 256. Après avoir vérifié l’entrée et initialisé la table de recherche, dans la boucle for principale, incrémentez le nombre d’occurrences dans l’emplacement correspondant dans la table de recherche, vérifiez si le nombre d’occurrences est dépassé. le nombre maximal actuel, si c’est le cas, met à jour le nombre maximal actuel et le caractère le plus fréquemment actuel. En fin de compte, retournez simplement le personnage le plus fréquent. La complexité temporelle de cette solution est O (N) et la complexité spatiale O (1).
char mostFrequentCharacter(char* str, int size) { char mosfFrequent; int counts[256], i, maxCount = 0; // in the case of invalid input, return some invalid character if(!str || size < 1) return '\0'; for(i = 0; i < 256; i++) counts[i] = 0; for (i = 0; i < size; i++) { counts[str[i]]++; if(counts[str[i]] > maxCount) { maxCount = counts[str[i]]; mostFrequent = str[i]; } } return mostFrequent; }
Voici un aperçu de l’algorithme:
Tout est fait en un seul passage sur la chaîne. Stockage 256 * taille d’octets entiers, mais vous avez “mémoire infinie” et c’est minuscule en comparaison 😉