Trouvez le plus grand intervalle qui a tous ses membres dans la liste dans O (n)

Question

On m'a demandé ceci dans une interview. Comment pouvons-nous trouver le plus grand intervalle de tous les membres dans une liste donnée avec une liste d'entiers?

Par exemple, la liste 1,3,5,7,4,6,10 donne alors la réponse serait [3, 7]. Parce qu'il a tous les éléments entre 3 et 7.

J'ai essayé de répondre mais je n'ai pas été convaincant. L’approche que j’ai choisie était d’abord de trier la liste, puis de la vérifier pour le plus grand intervalle. Mais on m'a demandé de le faire en O(n) .

Answer 1

Je connais une solution basée sur le hachage et la programmation dynamique. Laissez - f(x) soit la fonction de hachage. Le truc, c'est la table de hachage de la valeur. Envisager le plus long intervalle contenu dans la liste, qui commence ou se termine avec x. Alors h[f(x)] = y, où y est l'autre extrémité de cet intervalle. Notez que la longueur de cet intervalle seront abs( x - y ) + 1. La description d'algorithme explique pourquoi pour mémoriser la valeur.

Déplacez la souris sur la liste. Laissez - je être à jour de l'index, x := liste[ i ] - le nombre actuel. Maintenant

1. si h[f(x)] n'est pas vide, puis nous avons rencontré nombre de x avant. Rien à faire, continuer.

2. Vérifiez h[f(x-1)] et h[f(x+1)].

2.1. Si ils sont à la fois n'est pas vide, cela signifie que nous avons déjà rencontré x-1 et x+1, et nous savons que certains intervalles [a..x-1] et [x+1..b] que nous avons déjà rencontré dans la liste. Nous le savons parce que un=h[f(x-1)] et b=h[f(x+1)] par la définition d' h. Maintenant, quand nous avons eu x, cela signifie que nous avons maintenant réuni l'ensemble de l'intervalle [a,b], donc nous mettre à jour les valeurs comme suit: h[f(a)] := b et h[f(b)] := un.
Également mis h[f(x)] à une certaine valeur (disons x, de ne pas l'impact de la réponse), juste de sorte que la prochaine fois que nous rencontrons x dans la liste, nous les ignorer. x a déjà fait son travail.

2.2. Si un seul d'entre eux est défini, disons h[f(x-1)] = a, ce qui signifie que nous avons déjà rencontré un certain intervalle de temps [a..x-1], et maintenant elle est étendue avec x. Mise à jour sera h[f(a)] := x et h[f(x)] := un.

2.3. Si aucun n'est défini, cela signifie que nous avons rencontré ni x-1, ni x+1, et le plus grand intervalle contenant x nous avons déjà rencontré est le seul [x] lui-même. Donc, mettre h[f(x)] := x.

Enfin, pour obtenir la réponse, passer au-dessus de l'ensemble de la liste et de prendre le maximum abs( x - h[f(x)] ) + 1 pour tout x.

P. S. je suis familier avec ce problème, parce que j'ai été invité dans l'interview aussi :)

Answer 2

Si le tri n'est pas souhaitable, vous pouvez utiliser une combinaison de hachage carte et Disjoints-définir la structure de données.

Pour chaque élément dans la liste créer un nœud et de l'insérer dans la carte de hachage avec clé = valeur de l'élément. Alors interroger le hachage de la carte pour valeur+1 et la valeur-1. Si rien n'est trouvé, combiner le nœud actuel avec set(s) où les nœuds adjacents appartiennent. Lors de la fin de la liste, le plus grand ensemble correspond à la plus grande de l'intervalle.

Le temps de la complexité est O(N * α(N)) où α(N) est l'inverse de la fonction d'Ackermann.

Edit: en Fait Disjoints est trop puissant pour cette tâche simple. Solution par Grigor Guevorguyan ne l'utilise pas. De sorte qu'il est plus simple et plus efficace.

Answer 3

Vous pouvez le commerce hors de l'espace pour obtenir ce dans le temps linéaire.

1. Parcourez la liste pour les plus petits et les plus grandes valeurs, S et L.
2. Utiliser un tableau de booléens ou un bitvector, A, assez grand pour contenir (L - S + 1) entrées.
3. Passer par la liste de nouveau, le réglage de l'élément de true quand vous le voyez.
4. Maintenant, est triée. Passer par Un et de trouver le plus grand consécutives série de vraies valeurs.

Les premières étapes sont linéaires dans votre liste. La dernière est linéaire en la taille de l'Un, qui pourrait être importante par rapport à votre liste si vous avez quelques valeurs qui sont éloignés. Mais, puisque vous avez à traiter avec des entiers, Un est bornée.

Answer 4

1 idée: bien, je pense qu'il faut un peu trier la liste de toute façon, mais vous ne pouvez pas aller avec la fusion ou du tri rapide. Mais si vous avez de la mémoire, vous pouvez utiliser l'idée de comptage, de tri pour les entiers.

Ainsi, vous pouvez créer une matrice de 0 et de 1, de 0 à max int valeur, puis le remplir avec de si vous en avez de la valeur et puis trouver continue maximale de tableau

2 idée: créer le dictionnaire de valeurs, de trouver des min et max - O(N) opérations:

dict = {1: 1, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 10: 10}
min = 1
max = 10

ensuite, comme i in range(min, max) et de et de trouver le plus long en continu sous-ensemble

>>> d = [1, 3, 5, 7, 4, 6, 10]
>>> s = set(d)
>>> mind = min(d)
>>> maxd = max(d)
>>> a, b, j = 0, 0, 0

>>> for i in range(mind, maxd):
        if i not in s:
            if (b - a) < (i - j - 1):
                a, b = j, i - 1
            j = i + 1

>>> a, b
(3, 7)

mais cela pourrait être lent pour clairsemée des listes de ce genre [1, 9000, 100000]

EDIT: sur la base super grande réponse de Grigor Guevorguyan, voici le code pour O(N), dictionnaire de la solution en Python (j'adore la simplicité!!!)

l = [1, 3, 5, 7, 4, 6, 10]
d = {x:None for x in l}
print d
for (k, v) in d.iteritems():
    if v is not None: continue
    a, b = d.get(k - 1), d.get(k + 1)
    if a is not None and b is not None: d[k], d[a], d[b] = k, b, a
    elif a is not None: d[a], d[k] = k, a
    elif b is not None: d[b], d[k] = k, b
    else: d[k] = k
    print d

m = max(d, key=lambda x: d[x] - x)
print m, d[m]

sortie:

{1: None, 3: None, 4: None, 5: None, 6: None, 7: None, 10: None}
{1: 1, 3: None, 4: None, 5: None, 6: None, 7: None, 10: None}
{1: 1, 3: 3, 4: None, 5: None, 6: None, 7: None, 10: None}
{1: 1, 3: 4, 4: 3, 5: None, 6: None, 7: None, 10: None}
{1: 1, 3: 5, 4: 3, 5: 3, 6: None, 7: None, 10: None}
{1: 1, 3: 6, 4: 3, 5: 3, 6: 3, 7: None, 10: None}
{1: 1, 3: 7, 4: 3, 5: 3, 6: 3, 7: 3, 10: None}
{1: 1, 3: 7, 4: 3, 5: 3, 6: 3, 7: 3, 10: 10}
3 7

Answer 5

J'ai fabriqué une solution très simple à l'aide d'un HashSet. Depuis contains et remove O(1) opérations, vous pouvez simplement créer un nouvel intervalle à partir d'un ensemble aléatoire de l'élément et de 'développer' l'intervalle jusqu'à ce que vous découvrez sa pleine taille, la suppression d'éléments de l'ensemble, comme vous allez le long. La suppression est la clé, parce que c'est ce qui ne vous empêche de "répéter" tout d'intervalle.

Il peut être utile de penser à elle de cette façon - la liste a K intervalles, dont les tailles ajouter à N. Votre tâche est de découvrir ce que ces intervalles sont, sans répétition des intervalles ou des objets. C'est pourquoi le HashSet est parfait pour le travail - vous pouvez supprimer efficacement les éléments de l'ensemble que vous développez votre intervalles. Alors tout ce que vous devez faire est de garder une trace de l'intervalle le plus important, comme vous allez le long.

1. Mettre la liste en HashSet
2. Alors que l'ensemble est non-vide:
   1. supprimer un élément au hasard à partir de l'ensemble
   2. Définir l'intervalle à partir de cet élément
   3. Élargir l'intervalle comme suit:
      1. Définir i = interval.start-1
      2. Alors que le jeu contient i, retirez - i de l'ensemble et décrémenter les deux i et interval.start
      3. Répétez l'étape 2 dans l'autre sens (s'étendre à partir de interval.end)
   4. Si l'étendue de l'intervalle est plus grand que le précédent plus grand intervalle, enregistrement de la nouvelle-intervalle de l'intervalle le plus grand
3. De retour de l'intervalle le plus grand

Voici la solution en Java:

public class BiggestInterval {

    static class Interval {
        int start;
        int end;

        public Interval(int base) {
            this(base,base);
        }

        public Interval(int start, int end) {
            this.start = start;
            this.end = end;
        }

        public int size() {
            return 1 + end - start;
        }

        @Override
        public String toString() {
            return "[" + start + "," + end + "]";
        }
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        System.out.println(biggestInterval(Arrays.asList(1,3,5,7,4,6,10)));
    }

    public static Interval biggestInterval(List<Integer> list) {
        HashSet<Integer> set = new HashSet<Integer>(list);
        Interval largest = null;

        while(set.size() > 0) {
            Integer item = set.iterator().next();
            set.remove(item);

            Interval interval = new Interval(item);
            while(set.remove(interval.start-1)) {
                interval.start--;
            }
            while(set.remove(interval.end+1)) {
                interval.end++;
            }

            if (largest == null || interval.size() > largest.size()) {
                largest = interval;
            }
        }

        return largest;
    }
}