J'espère que je ne suis pas répondre à vos devoirs comme il l'a été plus d'un an que cette question a été posée. Voici une queue solution récursive qui prendra du log(len(a)+len(b)).
Hypothèse: Les entrées sont à droite. c'est à dire k est dans l'intervalle [0, len(a)+len(b)]
De la Base de cas:
- Si la longueur de l'un des tableaux est 0, la réponse est la k-ième élément de la deuxième matrice.
Étapes de réduction:
- Si le milieu de l'indice de + milieu de l'indice de b est inférieure à k
- Si le milieu de l'élément de a est plus grand que le milieu de l'élément de b, on peut ignorer le premier semestre de b, ajuster k.
- d'autre ignorer la première moitié d'un, ajuster k.
- Sinon si k est inférieur à la somme de la mi indices de a et b:
- Si le milieu de l'élément de a est plus grand que le milieu de l'élément de b, nous pouvons ignorer seconde moitié d'un
- le reste, nous pouvons ignorer la seconde moitié de b
Code:
def kthlargest(arr1, arr2, k):
if len(arr1) == 0:
return arr2[k]
elif len(arr2) == 0:
return arr1[k]
mida1 = len(arr1)/2
mida2 = len(arr2)/2
if mida1+mida2<k:
if arr1[mida1]>arr2[mida2]:
return kthlargest(arr1, arr2[mida2+1:], k-mida2-1)
else:
return kthlargest(arr1[mida1+1:], arr2, k-mida1-1)
else:
if arr1[mida1]>arr2[mida2]:
return kthlargest(arr1[:mida1], arr2, k)
else:
return kthlargest(arr1, arr2[:mida2], k)
Veuillez noter que ma solution est la création de nouvelles copies de petits tableaux dans chaque appel, ce qui peut être facilement éliminé par le seul passage de début et de fin des indices sur l'origine des tableaux.
