Déterminer s'il existe un nombre dans le tableau se produisant k fois

Question

Je veux créer un algorithme de division et de conquête (O (nlgn) runtime) pour déterminer s'il existe un nombre dans un tableau qui se produit k fois. Une contrainte sur ce problème est que seule une méthode de comparaison égalité/inégalité est définie sur les objets du tableau (c'est-à-dire que vous ne pouvez pas utiliser <,>). J'ai donc essayé un certain nombre d'approches, y compris la division du tableau en k morceaux de taille égale (environ). L'approche est similaire à trouver l'élément majoritaire dans un tableau, mais dans la majorité des cas lorsque vous divisez le tableau, vous savez que la moitié doit avoir un élément majoritaire si un tel élément existe. Des conseils ou des conseils que l'on pourrait fournir pour me mettre dans la bonne direction? EDIT: Pour éclaircir un peu, je me demande si le problème de trouver l'élément majoritaire en divisant le tableau en deux et en utilisant une solution récursive peut être étendu à d'autres situations où k peut être n/4 ou n/5 etc.

Peut-être que je devrais formuler la question en utilisant n/k à la place.

Answer 1

Ceci est impossible. Comme un simple exemple de pourquoi cela est impossible, considérons une entrée avec un tableau longueur-n, tous les éléments distincts, et k = 2. La seule façon de s'assurer qu'aucun élément n'apparaît deux fois est de comparer chaque élément à tous les autres éléments, ce qui prend du temps O (n^2). Tant que vous n'avez pas effectué toutes les comparaisons possibles, vous ne pouvez pas être sûr qu'une paire que vous n'avez pas comparée n'est pas réellement égale.