Recherche de plages contiguës dans des tableaux

Je pense que la suite de la solution en O(n) en temps à l'aide de O(n) de l'espace.

Commencer par mettre tous les éléments dans le tableau dans une table de hachage. Ensuite, créez une deuxième table de hachage qui stocke les éléments que nous avons "visité", qui est initialement vide.

Maintenant, itérer à travers le tableau d'éléments un à un. Pour chaque élément, vérifier si l'élément est dans le visité ensemble. Si oui, l'ignorer. Sinon, compter à partir de cet élément vers le haut. À chaque étape, vérifiez si le numéro est dans la principale de la table de hachage. Si oui, continuer en avant et de marquer la valeur actuelle dans le cadre de l'visité ensemble. Si non, stop. Ensuite, répétez cette procédure, à l'exception de comptage à la baisse. Ceci nous indique le nombre d'éléments contigus dans la plage contenant ce tableau de la valeur. Si nous gardons la trace de la plus grande plage d'trouvé cette façon, nous aurons une solution à notre problème.

L'exécution de la complexité de cet algorithme est O(n). Pour voir cela, notons que l'on peut construire la table de hachage dans la première étape en O(n) fois. Ensuite, lorsque nous avons commencer la numérisation de tableau de trouver le plus grand de la gamme, chaque scanné prend du temps proportionnel à la longueur de cet intervalle. Puisque la somme des longueurs des plages est le nombre d'éléments dans le tableau d'origine, et depuis nous n'avons jamais scan de la même gamme deux fois (parce que nous marquer chaque nombre que l'on visite), cette deuxième étape prend O(n) fois, pour une nette d'exécution de O(n).

EDIT: Si vous êtes curieux, j'ai un L'implémentation Java de cet algorithme, avec une analyse approfondie de pourquoi il fonctionne et pourquoi il a de la bonne exécution. Il explore également les quelques cas qui n'apparaissent pas dans la description initiale de l'algorithme (par exemple, comment traiter de dépassement d'entier).

Espérons que cette aide!

La réponse ci-dessus par le modèle va fonctionner, mais vous n'avez pas besoin d'une table de hachage. Le hachage pourrait prendre un certain temps en fonction de ce que l'algorithme que vous utilisez. Vous pouvez demander à l'intervieweur s'il y a un max de nombre entier peut être, puis créer un tableau de cette taille. Appel il existe[] Ensuite analyser arr et marque[i] = 1; Puis itérer sur[] garder la trace des 4 variables, la taille de l'actuel plus grand de la gamme, et le début de la plus grande plage, taille de la gamme actuelle, et le début de la plage actuelle. Quand vous voyez existent[i] = 0, de comparer l'état actuel de la gamme des valeurs de vs un plus grand éventail de valeurs et de mise à jour de la plus grande plage de valeurs si nécessaire.

Si il n'y a aucune valeur max, alors vous pourriez avoir à aller avec la méthode de hachage.

Un Haskell mise en œuvre de Grigor Guevorguyan de la solution, à partir d'un autre qui n'a pas la chance de les poster avant le question a été marqué comme un doublon...(met simplement à jour le hachage et la plus longue plage de mesure, tout en parcourant la liste)

import qualified Data.HashTable.IO as H
import Control.Monad.Random

f list = do 
  h <- H.new :: IO (H.BasicHashTable Int Int)
  g list (0,[]) h where
    g []     best h = return best
    g (x:xs) best h = do 
      m <- H.lookup h x
      case m of
        Just _     -> g xs best h
        otherwise  -> do 
          (xValue,newRange) <- test
          H.insert h x xValue
          g xs (maximum [best,newRange]) h
       where 
         test = do
           m1 <- H.lookup h (x-1)
           m2 <- H.lookup h (x+1)
           case m1 of
             Just x1 -> case m2 of
                          Just x2 -> do H.insert h (x-1) x2
                                        H.insert h (x+1) x1
                                        return (x,(x2 - x1 + 1,[x1,x2]))
                          Nothing -> do H.insert h (x-1) x
                                        return (x1,(x - x1 + 1,[x,x1]))
             Nothing -> case m2 of
                          Just x2 -> do H.insert h (x+1) x
                                        return (x2,(x2 - x + 1,[x,x2]))
                          Nothing -> do return (x,(1,[x]))

rnd :: (RandomGen g) => Rand g Int
rnd = getRandomR (-100,100)

main = do
  values <- evalRandIO (sequence (replicate (1000000) rnd))
  f values >>= print

De sortie:

*Main> main
(10,[40,49])
(5.30 secs, 1132898932 bytes)

J'ai lu beaucoup de solutions sur de multiples plateformes à ce problème et on retenu mon attention, car elle résout le problème, très élégant, et il est facile à suivre.

L'épine dorsale de cette méthode est de créer un ensemble/hachage qui prend O(n) le temps et à partir de là, tous les accès à l'ensemble/hash sera O(1). Comme le O-Notation omettre de termes constants, cet Algorithme peut encore être décrit comme O(n)

def longestConsecutive(self, nums):
    nums = set(nums)                    # Create Hash O(1)   
    best = 0
    for x in nums:                   
        if x - 1 not in nums:           # Optimization
            y = x + 1                   # Get possible next number
            while y in nums:            # If the next number is in set/hash
                y += 1                  # keep counting
            best = max(best, y - x)     # counting done, update best
    return best

Il est simple si vous avez exécuté plus simple avec des chiffres. Le Optimization étape, c'est un court-circuit à assurez-vous de commencer à compter, lorsque le nombre précis de la beginning d'une séquence.

Tous les Crédits à Stefan Pochmann.