169. Majority Element

LeetCode easy original: C# #array #csharp #easy #hash-table #leetcode #search

Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.

LeetCode Static

Дан mảng nums размера n, return element большинства.

element большинства — это element, который встречается более чем ⌊n / 2⌋ раз. Можно предположить, что element большинства всегда существует в mảngе.

Ví dụ:

Input: nums = [3,2,3]

Output: 3

C# lời giải

đã khớp/gốc

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

C++ lời giải

bản nháp tự động, xem lại trước khi gửi

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

Java lời giải

đã khớp/gốc

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();
    }
}

JavaScript lời giải

đã khớp/gốc

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

Python lời giải

đã khớp/gốc

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

Go lời giải

đã khớp/gốc

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 для отслеживания количества каждого elementа в mảngе.

2️⃣

Подсчет вхождений elementов:

Пройдите по mảngу nums, увеличивая счетчик в HashMap для каждого elementа.

3️⃣

Поиск elementа большинства:

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

😎

Vacancies for this task

việc làm đang hoạt động with overlapping task tags are đã hiển thị.

Tất cả việc làm

Chưa có việc làm đang hoạt động.