1
votes

Python 3 - Trouver les plages de tuple manquées

Disons que j'ai une plage int commençant à 0 et se termine à 48.

Comment puis-je trouver une séquence inclusive manquée à partir de tableaux donnés?

Given: [(10, 12), (12, 37)] 
Output: [(0,10),(37,48)]


Given: [(9, 15)] 
Output: [(0,9),(15,48)]


Given: [(0, 15), (15, 17), (17, 19), (21,25)] 
Output: [(19,21),(25,48)]


Given: [(23, 35),(40,47)] 
Output: [(0,23),(35,40),(47,48)]

python algorithm tuples range

2 commentaires

Bienvenue sur stackoverflow. qu'avez-vous essayé? afficher du code

Tout ce qui a été publié est une description du programme. Cependant, nous avons besoin que vous posiez une question sur la page Comment poser . Nous ne pouvons pas être sûrs de ce que vous attendez de nous. Veuillez modifier votre message pour inclure une question valide à laquelle nous pouvons répondre. Rappel: assurez-vous de savoir ce qui est sur le sujet ici en visitant le centre d'aide ; nous demander d'écrire le programme pour vous , les suggestions et les liens externes sont hors sujet .

3 Réponses :

3
votes

Nous devons seulement parcourir la plage de tuple triée , en recherchant les éléments manquants entre la position i dans la liste et le i + 1 code> position.

Le premier et le dernier tuples sont des cas de bord et doivent être considérés séparément, ainsi que le cas d'entrée vide. Voici un algorithme possible:

 find_missing_ranges([])
=> [(0, 48)]

find_missing_ranges([(0, 48)])
=> []

find_missing_ranges([(10, 12), (12, 37)])
=> [(0, 10), (37, 48)]

find_missing_ranges([(9, 15)])
=> [(0, 9), (15, 48)]

find_missing_ranges([(0, 15), (15, 17), (17, 19), (21, 25)])
=> [(19, 21), (25, 48)]

find_missing_ranges([(23, 35), (40, 47)])
=> [(0, 23), (35, 40), (47, 48)]
  Il fonctionne comme prévu avec l'exemple d'entrée: 
 def find_missing_ranges(tuples, start=0, end=48):
    # edge case: empty input
    if not tuples:
        return [(start, end)]
    ans = []
    # sort the input
    lst = sorted(tuples)
    # edge case: handle start of range
    if lst[0][0] != 0:
        ans.append((start, lst[0][0]))
    for i in range(len(lst) - 1):
        # normal case, find holes between tuples i and i+1
        if lst[i][1] != lst[i + 1][0]:
            ans.append((lst[i][1], lst[i + 1][0]))
    # edge case: handle end of range
    if lst[-1][1] != end:
        ans.append((lst[-1][1], end))
    return ans

2 commentaires

Ah, oui, je vois.

J'apprécie le temps que vous avez passé! Merci pour l'aide!

2
votes

Si vous parcourez simplement la liste et gardez une trace des valeurs de début et de fin, cela peut être fait assez proprement avec ce qui suit en supposant que la liste est triée. Vous ajoutez simplement un tuple au résultat si le tuple actuel [0] est supérieur à la valeur de départ. Vous vérifierez à la fin s'il vous reste des valeurs (si start ).

def getMissing(l, start, stop):
    newList = []
    for tup in l:
        if tup[0] > start:
            newList.append((start, tup[0]))
        start = tup[1]
    # add any left over values
    if start < stop:
        newList.append((start, stop))
    return newList

getMissing([(2, 12), (15, 46)], 0, 48)
# result: [(0, 2), (12, 15), (46, 48)]

0 commentaires

2
votes

Voici une méthode simple en parcourant chaque tuple et en vérifiant si le premier élément est supérieur au dernier élément le plus grand que nous ayons vu:

def get_gaps(tuples,l,r):
    """Return list of tuples representing gaps between l and r not covered by ranges in tuples."""

    # make sure tuples are sorted on first element
    tuples.sort()
    a= []

    for tup in tuples:
        if tup[0] > l:
            a.append((l,tup[0]))
        # update left marker to last seen (largest) element
        l = tup[1]

    # check final element of final tuple
    if r > l:
        a.append((l,r))

    return a

Remarque: cette méthode suppose que les tuples ne se chevauchent pas et peut ne pas produire des résultats corrects pour par exemple ((10, 20), (13,16))

1 commentaires

Ils ne le feront pas! Merci de votre aide!