Leetcode – Meilleur entretien –. Élément majoritaire

C'est un problème simple avec la description suivante :

Étant donné un tableau nums de taille n, renvoie l'élément majoritaire.

L'élément majoritaire est l'élément qui apparaît plus de ⌊n/2⌋ fois. Vous pouvez supposer que l'élément majoritaire existe toujours dans le tableau.

Exemple 1 :

Entrée : nums = [3,2,3]
Sortie : 3

Exemple 2 :

Entrée : nums = [2,2,1,1,1,2,2]
Sortie : 2

Contraintes :

n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109

À première vue, on penserait à faire une carte puis à rassembler celle qui montre le plus.

À la réflexion, si vous pouviez trier et obtenir celui qui apparaît le plus, cela ferait l'affaire.

Et avec ça, il existe un moyen encore plus simple. Si vous lisez attentivement la description, vous comprendrez qu'un élément majoritaire est celui qui apparaît sur plus de la moitié du tableau.

Dans cet esprit, si vous le triiez et récupériez l'index du milieu, cela résoudrait le problème :

class Solution {
    public int majorityElement(int[] nums) {

        // sort
        Arrays.sort(nums);

        // if by majority element it means that appears more than half of nums size
        // then picking the middle element would be the one that's a majority element
        return nums[nums.length / 2];
    }
}

Durée d'exécution : 4 ms, plus rapide que 54,53 % des soumissions en ligne Java pour Majority Element.

Utilisation de la mémoire : 53,5 Mo, soit moins de 9,23 % des soumissions en ligne Java pour Majority Element.

—

C'est ça ! S'il y a autre chose à discuter, n'hésitez pas à laisser un commentaire, si j'ai raté quelque chose, faites-le-moi savoir afin que je puisse mettre à jour en conséquence.

À la prochaine publication ! :)

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!