Ce qui suit est quelques méthodes pour vous présenter le nombre de numéros de tableau Java. Le contenu spécifique est le suivant:
Méthode 1:
Tri du tableau, puis la valeur intermédiaire est définitivement la valeur à trouver. Triez la complexité de temps minimale (tri rapide) O (NLOGNG), plus la traversée.
Méthode 2:
En utilisant une méthode de table de hachage, c'est-à-dire en comptant le nombre d'occurrences de chaque tableau et des nombres de sortie dont les occurrences sont supérieures à la longueur du tableau.
Méthode 3:
Le nombre d'occurrences dépasse la moitié de la longueur du tableau, indiquant que ce nombre apparaît plus de fois que la somme d'autres nombres.
Envisagez de supprimer deux nombres différents à chaque fois, le nombre d'occurrences dans les nombres restants dépasse toujours le nombre total. Répétez le processus constamment, excluez d'autres nombres et trouvez enfin le nombre avec plus de la moitié des occurrences. La complexité temporelle de cette méthode est O (n) et la complexité de l'espace est O (1).
Pour changer l'idée, cela peut être réalisé en comptant plutôt qu'à une véritable suppression physique. Pendant le processus de traversée du tableau, enregistrez deux valeurs, l'une est le nombre dans le tableau et l'autre est le nombre d'occurrences. Lorsque vous traversez le numéro suivant, si ce nombre est le même que le nombre précédemment enregistré, le nombre de fois est augmenté de 1, et s'il est différent, le nombre de fois est diminué de 1. Si le nombre de fois est 0, enregistrez le nombre suivant et définissez le nombre à 1. Étant donné que le nombre que nous recherchons apparaît plus de fois que la somme de tous les autres numéros, le nombre que nous recherchons doit être le nombre correspondant lorsque le nombre de fois est fixé à 1.
public int MoreShalf (int [] nums) {int result = 0; int count = 1; if (nums.length == 0) return -1; result = nums [0]; for (int i = 1; i <nums.length; i ++) {if (count == 0) {result = nums [i]; count = 1; continue;} if (résultat == nums [i]) count ++; résultat;}Méthode 4:
Tri amélioré de lignes rapides, mentionné précédemment, si un tableau est trié, le nombre en position centrale doit être la valeur que vous souhaitez. La complexité temporelle des tableaux de tri est O (NLOG (n)), mais pour cette question, il existe de meilleurs algorithmes qui peuvent être trouvés dans la complexité du délai O (n).
Dérivant de l'algorithme de tri rapide, la méthode partition () est la méthode la plus importante. Cette méthode renvoie un index, ce qui peut garantir que le nombre en position d'index est trié. Le numéro à gauche de l'index est inférieur au nombre où l'index est situé, et le nombre à droite de l'index est supérieur au nombre où l'index est situé. Ensuite, cette question peut être résolue en utilisant cette idée.
Index de retour via partition (). Si index == mid, cela signifie que la médiane du tableau a été trouvée; Si indexMID, cela signifie que la médiane se situe entre [start, index-1]. Je sais que la fin de la boucle d'index == mid est obtenue.
public int partition (int [] nums, int start, int fin) {int pivotkey = nums [start]; int origine = start; while (start <end) {while (start <end && nums [end]> = pivotkey) end -; while (start <end && nums [start] <pivotkey) start ++; swap (nums, start, fin);};} swap (nums, start, end); swap (nums, origine, end); return end;} p int [] swap (int [] ints, int x, int y) {int temp = ints [x]; INTS [X] = INTS [Y]; INTS [y] = temp; retour INTS; } public int MoreThanHalf (int [] nums) {if (nums.length == 0) return -1; int start = 0; int end = nums.length-1; int index = partition (nums, start, end); int mid = nums.length / 2; while (index! = mid) {if (index> mid) // index a obtenu à ajuster le tableau Partition (nums, start, index-1); else {// Ajustez autrement l'index du tableau de l'index + 1 à fin section = partition (nums, index + 1, end);}} return nums [index];}Le contenu ci-dessus présente le contenu pertinent du code Java qui implémente des nombres apparaissant plus de la moitié des fois dans un tableau. J'espère que ce sera utile à tous!