ADSA - Tuto 1 - Exo4 - b - Proposition d'algo en O(n), C#

ADSA - Tuto 1 - Exo4 - b - Proposition d'algo en O(n)

//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Rextester
{
    public class Program
    {
        public static void Main(string[] args)
        {
            //Demonstration
            //Dans le tableau ci-dessous en l'état actuel => 67 est l'entier apparaissant le plus avec le nombre d'occurences 3
            int[] tab = new int[] { 1000, -2, -12, 35, -100, 67, 32, 1000, 67, 35, 67, -2 };
            Console.WriteLine("Nombre d'occurences de l'entier le plus fréquent:{0}", Compte_nb_max_occurences(tab));
        }
        /*
        / Retourne le nombre d'occurences de l'entier le plus fréquent de tab
        /La complexité de l'algorithme est O(n) avec ici n la longueur de tab
        */
        public static int Compte_nb_max_occurences(int[] tab)
        {
            int[] tab_occurences;  //O(1)
            int min = tab[0];  //O(1)
            int max = tab[0];  //O(1)
            int nb_max_occurences=0;  //O(1)
            //Trouvons le plus petit et le plus grand entier de tab
            for (int i = 1; i < tab.Length; i++)  //O(n)
            {
                if (tab[i] > max)  //O(1)
                    max = tab[i];  //O(1)
                if (tab[i] < min)  //O(1)
                    min = tab[i];  //O(1)
            }
            //Allouons un tableau d'entier. 
            //L'index d'un entier correspondra à un nombre de tab, la valeur, elle, correspondra au nombre d'occurences du nombre dans tab
            tab_occurences = new int[max - min + 1];  //0(1), en c# les int d'un tab de int sont initialisés à 0
            for (int i = 0; i < tab.Length; i++)  //O(n)
            {
                tab_occurences[tab[i] - min]++;  //O(1)
            }
            //parcourons tab, pour chaque int de tab, regardons son nombre d'occurences, 
            //s'il est superieur à max => max prend le nombre d'occurences de cet int
            for (int i = 1; i < tab.Length; i++)  //O(n)
            {
                if (tab_occurences[tab[i] - min]>nb_max_occurences)  //O(1)
                    nb_max_occurences = tab_occurences[tab[i] - min];  //O(1)
            }
            return nb_max_occurences; //On retourne le nombre d'occurences de l'entier apparaissant le plus de fois dans tab
        }
    }
}


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development