Trouver un numéro où il apparaît exactement N/2 fois

Il y a une constante de temps de la solution si vous êtes prêt à accepter une faible probabilité d'erreur. Au hasard des échantillons de deux valeurs de l'array, si elles sont les mêmes, vous avez trouvé la valeur que vous recherchez. À chaque étape, vous avez une 0.75 probabilité de ne pas finir. Et parce que pour chaque epsilon, il existe un n tel que (3/4)^n < eps, on peut déguster au plus n fois et retourner une erreur si nous n'avons pas trouvé une paire.

Également remarquer que, si nous continuons d'échantillonnage jusqu'à ce que nous avons trouvé une paire, le temps d'exécution est constante, mais le cas le pire temps d'exécution n'est pas bornée.

Je pense que vous avez tout simplement besoin d'analyser à travers le tableau de tenir un carnet de commandes de deux éléments. En tant que N/2 sont à égalité, et le repos est garanti pour être distincts, il doit y avoir un endroit où je dans votre tableau où

a[i] == a[i-1] OR a[i] == a[i-2]

itérer une fois par le biais de votre tableau et vous avez la complexité de près de 2*N, qui doit être bien à l'intérieur de O(N).

Cette réponse est un peu similaire à la réponse par Ganesh M et Dougie, mais je pense un peu plus simple.

Pierre est tout à fait exact. Voici une manière plus formelle de renouvelle sa preuve:

Laisser l'ensemble S est un ensemble contenant N éléments. C'est l'union de deux ensembles: p, qui contient un symbole α répété N/2 fois, et q, qui contient N/2 des symboles uniques ω₁..ω_n/2. S = p ∪ q.

Supposons qu'il existe un algorithme qui permet de détecter votre dupliqué nombre en log(n) comparaisons dans le pire des cas pour tous les N > 2. Dans le pire des cas, signifie que il n'existe aucune sous-ensemble r ⊂ S tel que |r| = log₂ N, où α ∉ r.

Cependant, parce que S = p ∪ q, il y a |p| de nombreux éléments ≠ α dans S. |p| = N/2, donc ∀ N/2 tel que N/2 ≥ log₂N, il doit exister au moins un ensemble r ⊂ S tel que |r| = log₂N et α ∉ r. C'est le cas pour tout N ≥ 3. Ce qui contredit l'hypothèse ci-dessus, donc il ne peut pas être un tel algorithme.

CQFD.

La réponse est simple.. et peut être réalisé dans le pire des cas (n/2 + 1) comparaisons

1. Comparer deux à deux les premier (n-2) numéros, qui est, de comparer nos. à 0 et 1, puis 2 et 3 et ainsi de suite... total n/2 -1 comparaisons.
   Si nous trouvons des chiffres identiques dans les comparaisons ci-dessus.. nous avons la répétition de nombre... else:

2. De prendre l'un des deux derniers numéros restants (disons dernière seconde j'ai pris) et de la comparer avec les chiffres dans la dernière seconde paire.. si le match se produit..deuxième pas durer. est le repated, autrement dernière est la répétition d'un... dans tous les 2 comparaisons.

Total de comparaisons = n/2 - 1 + 2 =n/2 + 1 (pire des cas)
Je ne pense pas qu'il y est tout de O(log n) une méthode pour atteindre cet

Si je suis la compréhension du problème correctement: tout ce que nous savons à propos de la matrice est sa longueur et qu'il a (N/2)+1 éléments uniques, où 1 élément est répété N/2 fois(dans aucun ordre particulier).

Je pense que cette souffre d'une limite physique de O(N) pour la solution que vous ne pouvez pas vraiment affirmer (pour un générique de tableau) que vous avez trouvé le numéro, sans en trouver au moins 2 de ce même numéro. Je ne pense pas qu'il existe une recherche pour un non ordonnée tableau qui peut détecter un duplicata en O(logN) (corrigez-moi si je me trompe). Vous aurez toujours besoin d'en lire au moins N/2 +1 éléments dans le pire des cas.

Supposons que vous avez un python algorithme comme ceci:

import math
import random

def find_duplicate(arr, gap):
    cost, reps = 0, 0
    while True:
        indexes = sorted((random.randint(0,len(arr)-i-1) for i in xrange(gap)), reverse=True)
        selection = [arr.pop(i) for i in indexes]
        selection_set = set(selection)
        cost += len(selection)
        reps += 1
        if len(selection) > len(selection_set):
            return cost, reps

L'idée est que arr est votre ensemble de valeurs et de écart est le logarithme en base 2 de la taille. Chaque fois que vous sélectionnez écart éléments et de voir si il y a des doublons. Si oui, de retour de vos coûts (en nombre d'éléments examinés) et le nombre d'itérations (où vous examinez log2(taille) d'éléments par itération). Sinon, regardez un autre écartde la taille d'ensemble.

Le problème avec l'analyse comparative de cet algorithme est que la création des données, chaque passage dans la boucle et l'altération des données est coûteuse, en supposant une grande quantité de données. (Au départ, je faisais 1 000 000 éléments de 10 000 000 d'itérations.)

Donc, nous allons réduire à un équivalent problème. Les données sont transmises en tant que n/2 éléments uniques et n/2 éléments répétés. L'algorithme choisit au hasard des indices de log2(n) des éléments et des contrôles pour les doublons. Maintenant, nous n'avons même pas à créer les données et de supprimer des éléments examinés: il nous suffit de vérifier si nous avons deux ou plusieurs indices sur le point à mi-chemin. Sélectionnez écart index, vérifiez 2 ou plus, le point à mi-chemin: de retour si trouvé, sinon répéter.

import math
import random

def find_duplicate(total, half, gap):
    cost, reps = 0, 0
    while True:
        indexes = [random.randint(0,total-i-1) for i in range(gap)]
        cost += gap
        reps += 1
        above_half = [i for i in indexes if i >= half]
        if len(above_half) >= 2:
            return cost, reps
        else:
            total -= len(indexes)
            half -= (len(indexes) - len(above_half))

Maintenant le code comme ceci:

if __name__ == '__main__':
    import sys
    import collections
    import datetime
    for total in [2**i for i in range(5, 21)]:
        half = total //2
        gap = int(math.ceil(math.log10(total) /math.log10(2)))
        d = collections.defaultdict(int)
        total_cost, total_reps = 0, 1000*1000*10
        s = datetime.datetime.now()
        for _ in xrange(total_reps):
            cost, reps = find_duplicate(total, half, gap)
            d[reps] += 1
            total_cost += cost
        e = datetime.datetime.now()
        print "Elapsed: ", (e - s)
        print "%d elements" % total
        print "block size %d (log of # elements)" % gap
        for k in sorted(d.keys()):
            print k, d[k]
        average_cost = float(total_cost) /float(total_reps)
        average_logs = average_cost /gap
        print "Total cost: ", total_cost
        print "Average cost in accesses: %f" % average_cost
        print "Average cost in logs: %f" % average_logs
        print

Si vous essayez ce test, vous verrez que le nombre de fois que l'algorithme a faire des sélections multiples diminue avec le nombre d'éléments de données. C'est, votre coût moyen dans les journaux asymptotiquement approches 1.

elements    accesses    log-accesses
32          6.362279    1.272456
64          6.858437    1.143073
128         7.524225    1.074889
256         8.317139    1.039642
512         9.189112    1.021012
1024        10.112867   1.011287
2048        11.066819   1.006075
4096        12.038827   1.003236
8192        13.022343   1.001719
16384       14.013163   1.000940
32768       15.007320   1.000488
65536       16.004213   1.000263
131072      17.002441   1.000144
262144      18.001348   1.000075
524288      19.000775   1.000041
1048576     20.000428   1.000021

Maintenant, est-ce un argument en faveur de l'idéal algorithme étant log2(n) dans la moyenne des cas? Peut-être. Ce n'est certainement pas de même dans le pire des cas.

Aussi, vous n'avez pas à choisir log2(n) éléments à la fois. Vous pouvez choisir 2 et vérifier l'égalité (mais dans le cas dégénéré, vous ne trouverez pas la duplication du tout), ou vérifier qu'un numéro de plus pour la duplication. À ce stade, tous les algorithmes que de sélectionner des éléments et vérifier la duplication à l'identique, ne variant que dans la façon dont beaucoup de qu'ils choisir et comment elles d'identifier les doublons.

Ici est Ne Johe réponse en Ruby:

#!/usr/bin/ruby1.8

def find_repeated_number(a)
  return nil unless a.size >= 3
  (0..a.size - 3).each do |i|
    [
      [0, 1],
      [0, 2],
      [1, 2],
    ].each do |j1, j2|
      return a[i + j1] if a[i + j1] == a[i + j2]
    end
  end
end

p find_repeated_number([1, 1, 2])   # => 1
p find_repeated_number([2, 3, 2])   # => 1
p find_repeated_number([4, 3, 3])   # => 1

O(n)

Similaire à https://stackoverflow.com/a/1191881/199556 explication.

Nous allons comparer les 3 éléments(3 opération de comparaison) dans le pire des cas "même" élément n'apparaît qu'une fois.
Nous avons donc réduire la queue par 3 et de réduire le nombre de "même" éléments par un.

À l'étape finale(après k itérations) notre queue contiendra (n/2) - k "même" éléments. Nous allons comparer la longueur de la queue.

D'une part, il n-3k
d'autre part (n/2) - k + 1. Dernière unsame éléments peuvent exister.

n-3k = (n/2) - k + 1

k = 1/4*(n-2)

Après k itérations, nous allons sûrement avoir raison.

Nombre de comparaisons 3/4*(n-2)

C'est une mauvaise question d'entrevue.

1. Vous ne savez pas la réponse vous-même.
2. Il n'a pas de cas d'affaires derrière elle, de sorte que vous aurez de la difficulté à l'expliquer, à le candidat.

Principalement en raison de la première. Que recherchez-vous? Que le candidat devra venir avec ce O(log n) solution vous ne savez pas existe? Si vous vous posez StackOverflow, est-ce quelque chose que vous pouvez raisonnablement s'attendre à un candidat dans une interview?