TP2---POO

#include <iostream>
#include <vector>
#include <time.h>
#include <stdlib.h> // rand

/* Taille du vecteur */
int const N = 9;

static bool compare(std::map<int,int>::value_type a, std::map<int,int>::value_type b) {
    return a.second < b.second;
}

/* Algorithme avec le conteneur map */
int map_majoritaire(std::vector<int> arr) {
    std::map<int,int> maj;
    for(std::vector<int>::iterator it = arr.begin(); it != arr.end(); it++)
        ++maj[*it];
    std::map<int,int>::iterator result= std::max_element(maj.begin(), maj.end(), compare);
    if((*result).second > arr.size() / 2)
        return (*result).first;
    else
        return -1;
}


int algorithme_tri(std::vector<int> arr) {
    std::sort(arr.begin(), arr.end());
    int taille = arr.size();
    int i = 0;
    int candidat, cpt;
    while(i <= taille/2) {
        candidat = arr[i];
        std::cout << i << " " << i+taille/2 << std::endl;
        if(arr[i+taille/2] == candidat)
            return candidat;
        i++;
    }
    return -1;
}

int algorithme_naif(std::vector<int> arr) {
    int taille = arr.size();
    int majoritaire, cpt;
    for (int i = 0; i < taille; i++) {
        majoritaire = arr[i];
        cpt = 0;
        for (int j = 0; j < taille; j++) {
            if (arr[j] == majoritaire)
                cpt++;
        }
        if (cpt > taille/2)
            return majoritaire;
    }
    return -1;
}


int main() {

    srand(time(NULL));
    // Création d'un vecteur avec constructeur par défaut
    std::vector<int> v;

    for(int i = 0; i < N; i++) {
        // Ajout d'une valeur aléatoire en fin de vecteur
        v.push_back(rand() % 10 + 1);
        std::cout << v[i] << " ";
    }

    std::cout << std::endl;
    std::cout << "Element majoritaire simple : " << algorithme_naif(v) << std::endl;
    std::cout << "Element majoritaire avec tri : " << algorithme_tri(v) << std::endl;
    std::cout << "Element majoritaire Boyer-Moore : " << element_majoritaire(v) << std::endl;

    return 0;

}