Leetcode – Top-Interview –. Mehrheitselement

Es ist ein einfaches Problem, wenn die Beschreibung so lautet:

Gibt bei einem gegebenen Array nums der Größe n das Mehrheitselement zurück.

Das Mehrheitselement ist das Element, das mehr als ⌊n / 2⌋ Mal vorkommt. Sie können davon ausgehen, dass das Mehrheitselement immer im Array vorhanden ist.

Beispiel 1:

Eingabe: nums = [3,2,3]
Ausgabe: 3

Beispiel 2:

Eingabe: nums = [2,2,1,1,1,2,2]
Ausgabe: 2

Einschränkungen:

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

Auf den ersten Blick würden Sie darüber nachdenken, eine Karte zu erstellen und dann diejenige zu sammeln, die am meisten zeigt.

Bei genauerer Betrachtung würde es reichen, wenn Sie die Liste sortieren und diejenige finden könnten, die am häufigsten angezeigt wird.

Und damit gibt es noch einen einfacheren Weg. Wenn Sie die Beschreibung sorgfältig lesen, werden Sie verstehen, dass ein Mehrheitselement eines ist, das mehr als die Hälfte des Arrays vorkommt.

Vor diesem Hintergrund würde das Problem gelöst, wenn Sie es sortieren und den Index der Mitte greifen würden:

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];
    }
}

Laufzeit: 4 ms, schneller als 54,53 % der Java-Online-Einreichungen für Majority Element.

Speichernutzung: 53,5 MB, weniger als 9,23 % der Java-Online-Einreichungen für Majority Element.

—

Das ist es! Wenn es sonst noch etwas zu besprechen gibt, können Sie gerne einen Kommentar hinterlassen. Wenn ich etwas verpasst habe, lassen Sie es mich wissen, damit ich es entsprechend aktualisieren kann.

Bis zum nächsten Beitrag! :)

Das obige ist der detaillierte Inhalt vonLeetcode – Top-Interview –. Mehrheitselement. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!