Voici comment j'ai pensé cela. Puisque c'est un problème d'éducation, je vous suggère d'arrêter de lire si l'un des points vous fait penser: «Ah, je n'y avais pas pensé, je peux penser plus loin dans ce sens tout seul».
1) Même observation que sdcwc: avec un léger problème éventuel à savoir s'il commence à 0 ou 1, la base de données peut être considérée comme une matrice triée. Je demande l'élément 0, je reçois le plus petit. Je demande 12, je reçois le 13 plus petit. Etc. Je trouve cela plus facile à visualiser.
2) Nous savons que nous recherchons un algorithme O (log n). Cela veut dire que grosso modo, nous sommes à la recherche d'une des deux choses:
Soit nous commençons par le calcul le plus petit élément, calculer alors le 2ème plus petit, plus petit 4, 8, etc., jusqu'à ce que nous sommes en à la taille que nous voulons, chaque étape dans le temps constant. Cela ne me semble pas prometteur. Ou nous partons d'un problème de taille n alors nous effectuons une opération à temps constant qui nous permet de résoudre le problème original en résolvant un problème de taille n/2.Évidemment, nous pouvons résoudre le problème pour n = 1 en temps constant, pour compléter l'algorithme. Cela semble un peu plus plausible.
En fait, il ne doit pas nécessairement être n/2 à chaque fois. Il pourrait être n/3, ou 999 * n/1000, et le résultat sera toujours O (log n). Mais il n'y a pas de mal à chercher n/2 en premier.
3) Comment allons-nous réduire le problème comme ça? Eh bien, si nous pouvons escompter/supprimer m éléments du début d'un tableau ou l'autre comme étant plus petit que le kth plus petit, alors nous pouvons trouver le (km) ème plus petit élément de la paire de tableaux résultante, et ce sera le kth plus petit des tableaux originaux. 4) Enfin, l'observation de percée est que si le mème plus petit élément du tableau A est plus petit que le mième plus petit élément du tableau B, alors ce mème élément de A ne peut pas être le (2m) plus petit élément du tableau deux tableaux combinés. Il est plus petit que cela (ou de valeur égale: je ne suis pas sûr si "aucune répétition" signifie "pas de répétitions dans chaque base de données", ou "pas de répétitions entre les bases de données combinées"), puisqu'il y a au maximum 2 * 1) éléments strictement plus petit que dans les deux tableaux combinés.
Sauf si j'ai fait une erreur, le reste est en train de coder. Avec un petit argument supplémentaire pour rendre compte de l'off-by-1 lorsque k est impair, cette solution est en fait O (log k), qui est O (log n) puisque k < = 2 * n.
bien expliqué – user2290820