169. Majority Element

public class Solution {
    private Dictionary<int, int> countNums(int[] nums) {
        var counts = new Dictionary<int, int>();
        foreach (int num in nums) {
            if (!counts.ContainsKey(num)) {
                counts.Add(num, 1);
            } else {
                counts[num]++;
            }
        }
        return counts;
    }
    public int MajorityElement(int[] nums) {
        var counts = countNums(nums);
        foreach (var count in counts) {
            if (count.Value > nums.Length / 2)
                return count.Key;
        }
        return 0;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private unordered_map<int, int> countNums(vector<int>& nums) {
        var counts = new unordered_map<int, int>();
        foreach (int num in nums) {
            if (!counts.count(num)) {
                counts.push_back(num, 1);
            } else {
                counts[num]++;
            }
        }
        return counts;
    }
    public int MajorityElement(vector<int>& nums) {
        var counts = countNums(nums);
        foreach (var count in counts) {
            if (count.Value > nums.size() / 2)
                return count.Key;
        }
        return 0;
    }
}

class Solution {
    private Map<Integer, Integer> countNums(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
        for (int num : nums) {
            if (!counts.containsKey(num)) {
                counts.put(num, 1);
            } else {
                counts.put(num, counts.get(num) + 1);
            }
        }
        return counts;
    }

    public int majorityElement(int[] nums) {
        Map<Integer, Integer> counts = countNums(nums);

        Map.Entry<Integer, Integer> majorityEntry = null;
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (entry.getValue() > nums.length / 2) return entry.getKey();
        }

        return majorityEntry.getKey();
    }
}

var majorityElement = function (nums) {
    let counts = {};
    for (let num of nums) {
        if (!counts[num]) {
            counts[num] = 1;
        } else {
            counts[num]++;
        }
    }

    for (let num in counts) {
        if (counts[num] > nums.length / 2) return Number(num);
    }
    return 0;
};

class Solution:
    def majorityElement(self, nums):
        counts = collections.Counter(nums)
        return max(counts.keys(), key=counts.get)

func majorityElement(nums []int) int {
    counts := make(map[int]int)
    for _, num := range nums {
        if _, ok := counts[num]; ok {
            counts[num]++
        } else {
            counts[num] = 1
        }
    }
    for num, count := range counts {
        if count > len(nums)/2 {
            return num
        }
    }
    return 0
}

Algorithm

1️⃣

Использование HashMap для подсчета:

Создайте HashMap для отслеживания количества каждого элемента в массиве.

2️⃣

Подсчет вхождений элементов:

Пройдите по массиву nums, увеличивая счетчик в HashMap для каждого элемента.

3️⃣

Поиск элемента большинства:

Определите элемент большинства, просмотрев HashMap и найдя ключ с максимальным значением, которое должно быть больше ⌊n / 2⌋

😎