Le plus commun élément dans un tableau / Trouver de la majorité relative, de façon déterministe en temps O(n) en temps et O(1) de l'espace?

Ce n'est pas une réponse complète, mais il devrait aider à jeter une certaine lumière sur les raisons de ce problème est difficile.

Considérons que nous voulons concevoir un algorithme, qui fait un balayage sur le tableau (dans l'ordre) de trouver l'élément commun. Lors de l'exécution de notre algorithme, il est permis de garder une certaine structure de données S. Nous allons voir comment beaucoup d'informations, il y a dans S, et donc si l'on est capable de le contenir dans O(1) mémoire.

Dire que notre algorithme a traité le premier k éléments de la matrice. Maintenant S peut nous dire la plupart élément commun dans la gamme a[0..k]. Cependant, dire que nous savions que le k+1'st élément, nous savons aussi le plus commun élément dans la gamme a[0..k+1]. Si elle ne pouvait pas le cas, notre algorithme ne fonctionne pas si n était k+1. Plus généralement, la connaissance des éléments a[k..m] et S, nous savons que la plupart élément commun dans a[0..m].

On peut utiliser l'argument ci-dessus pour extraire des informations à partir de S. Dis, on travaille avec des entiers dans la gamme [0,u] (il doit y avoir de gamme si le tableau d'origine a pris l'espace O(n)). Si l'origine de la plupart élément commun est 5, puis nous ajoutons 0's jusqu'à ce que le plus commun élément change. Si cela a pris c zéros, a[0..k] doit avoir contenu c plus 5's que 0'. En répétant cet argument nous recevons beaucoup d'équations linéaires qui nous permet de résoudre de dire exactement combien de fois chacun des éléments [0,u] étaient présents dans a[0..k].

Cela nous dit que toute structure de données qui effectue un balayage, pourrait tout aussi bien stocker le nombre de toutes les le vu des éléments (dans certains compressé façon). Si vous êtes intéressé par les maths, la stockées après avoir vu n nombres est log(n+u-1 choose n) qui est le journal de bord de le nombre de façons de partition n impossible de distinguer les éléments dans u distinguer les bacs. C'est plus que log(u^n/n!) >= nlogu-nlogn.

Conclusion: Tout algorithme qui ne fait qu'un passage de la matrice devrez utiliser autant de mémoire qu'il faut pour stocker tous les comtes vu jusqu'à présent. Si n est petite par rapport à u cela correspond à stocker n mots de la mémoire.

(Eh bien, au lieu de la mémoire supplémentaire, nous pouvons également remplacer le tableau existant).

Il y a beaucoup plus à découvrir ici. E. g. comment passes multiples et affectent les arguments ci-dessus. Cependant, je pense que je devrais arrêter à ce point :), mais il ne semble pas probable pour moi que tout le temps linéaire de l'algorithme, avec un grand u, sera en mesure de s'en tirer avec O(1) de la mémoire supplémentaire.

OriginalL'auteur Thomas Ahle

c'est mon script pour lire plus commun élément dans un tableau

<?php

class TestClass {

    public $keyVal;
    public $keyPlace = 0;

    //put your code here
    public function maxused_num($array) {
        $temp = array();
        $tempval = array();
        $r = 0;
        for ($i = 0; $i <= count($array) - 1; $i++) {
            $r = 0;
            for ($j = 0; $j <= count($array) - 1; $j++) {
                if ($array[$i] == $array[$j]) {
                    $r = $r + 1;
                }
            }
            $tempval[$i] = $r;
            $temp[$i] = $array[$i];
        }
        //fetch max value
        $max = 0;
        for ($i = 0; $i <= count($tempval) - 1; $i++) {
            if ($tempval[$i] > $max) {
                $max = $tempval[$i];
            }
        }
        //get value 
        for ($i = 0; $i <= count($tempval) - 1; $i++) {
            if ($tempval[$i] == $max) {
                $this->keyVal = $tempval[$i];
                $this->keyPlace = $i;
                break;
            }
        }

        //1.place holder on array $this->keyPlace;
        //2.number of reapeats $this->keyVal;
        return $array[$this->keyPlace];
    }

}

$catch = new TestClass();
$array = array(1, 1, 1, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 3, 1, 2, 3, 1, 1, 2, 5, 7, 1, 9, 0, 11, 22, 1, 1, 22, 22, 35, 66, 1, 1, 1);
echo $catch->maxused_num($array);

OriginalL'auteur ashish yadav