229. Majority Element II

LeetCode medium оригинал: C# #array #csharp #leetcode #medium #search

LeetCode Static

Дан массив целых чисел размера n, найдите все элементы, которые встречаются более ⌊ n/3 ⌋ раз.

Пример

Input: nums = [3,2,3]

Output: [3]

C# решение

сопоставлено/оригинал

public class Solution {
    public IList<int> MajorityElement(int[] nums) {
        int count1 = 0, count2 = 0;
        int? candidate1 = null, candidate2 = null;
        
        foreach (int n in nums) {
            if (candidate1.HasValue && candidate1 == n) {
                count1++;
            } else if (candidate2.HasValue && candidate2 == n) {
                count2++;
            } else if (count1 == 0) {
                candidate1 = n;
                count1 = 1;
            } else if (count2 == 0) {
                candidate2 = n;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }
        
        count1 = 0;
        count2 = 0;
        
        foreach (int n in nums) {
            if (candidate1.HasValue && candidate1 == n) count1++;
            if (candidate2.HasValue && candidate2 == n) count2++;
        }
        
        IList<int> result = new List<int>();
        int nLength = nums.Length;
        if (count1 > nLength / 3) result.Add(candidate1.Value);
        if (count2 > nLength / 3) result.Add(candidate2.Value);
        
        return result;
    }
}

C++ решение

auto-draft, проверить перед отправкой

#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:
    public vector<int> MajorityElement(vector<int>& nums) {
        int count1 = 0, count2 = 0;
        int? candidate1 = null, candidate2 = null;
        
        foreach (int n in nums) {
            if (candidate1.HasValue && candidate1 == n) {
                count1++;
            } else if (candidate2.HasValue && candidate2 == n) {
                count2++;
            } else if (count1 == 0) {
                candidate1 = n;
                count1 = 1;
            } else if (count2 == 0) {
                candidate2 = n;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }
        
        count1 = 0;
        count2 = 0;
        
        foreach (int n in nums) {
            if (candidate1.HasValue && candidate1 == n) count1++;
            if (candidate2.HasValue && candidate2 == n) count2++;
        }
        
        vector<int> result = new List<int>();
        int nLength = nums.size();
        if (count1 > nLength / 3) result.push_back(candidate1.Value);
        if (count2 > nLength / 3) result.push_back(candidate2.Value);
        
        return result;
    }
}

Java решение

сопоставлено/оригинал

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int count1 = 0, count2 = 0;
        Integer candidate1 = null, candidate2 = null;
        
        for (int n : nums) {
            if (candidate1 != null && candidate1 == n) {
                count1++;
            } else if (candidate2 != null && candidate2 == n) {
                count2++;
            } else if (count1 == 0) {
                candidate1 = n;
                count1 = 1;
            } else if (count2 == 0) {
                candidate2 = n;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }
        
        count1 = 0;
        count2 = 0;
        
        for (int n : nums) {
            if (candidate1 != null && candidate1 == n) count1++;
            if (candidate2 != null && candidate2 == n) count2++;
        }
        
        List<Integer> result = new ArrayList<>();
        int n = nums.length;
        if (count1 > n / 3) result.add(candidate1);
        if (count2 > n / 3) result.add(candidate2);
        
        return result;
    }
}

JavaScript решение

сопоставлено/оригинал

class Solution {
    majorityElement(nums) {
        let count1 = 0, count2 = 0;
        let candidate1 = null, candidate2 = null;
        
        for (let n of nums) {
            if (candidate1 !== null && candidate1 === n) {
                count1++;
            } else if (candidate2 !== null && candidate2 === n) {
                count2++;
            } else if (count1 === 0) {
                candidate1 = n;
                count1 = 1;
            } else if (count2 === 0) {
                candidate2 = n;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }
        
        count1 = 0;
        count2 = 0;
        
        for (let n of nums) {
            if (candidate1 !== null && candidate1 === n) count1++;
            if (candidate2 !== null && candidate2 === n) count2++;
        }
        
        const result = [];
        const nLength = nums.length;
        if (count1 > nLength / 3) result.push(candidate1);
        if (count2 > nLength / 3) result.push(candidate2);
        
        return result;
    }
}

Python решение

сопоставлено/оригинал

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        count1, count2, candidate1, candidate2 = 0, 0, None, None
        
        for n in nums:
            if candidate1 is not None and candidate1 == n:
                count1 += 1
            elif candidate2 is not None and candidate2 == n:
                count2 += 1
            elif count1 == 0:
                candidate1, count1 = n, 1
            elif count2 == 0:
                candidate2, count2 = n, 1
            else:
                count1 -= 1
                count2 -= 1
        
        count1, count2 = 0, 0
        for n in nums:
            if candidate1 == n:
                count1 += 1
            if candidate2 == n:
                count2 += 1
        
        result = []
        n = len(nums)
        if count1 > n // 3:
            result.append(candidate1)
        if count2 > n // 3:
            result.append(candidate2)
        
        return result

Go решение

сопоставлено/оригинал

package main

func majorityElement(nums []int) []int {
    count1, count2 := 0, 0
    var candidate1, candidate2 *int
    
    for _, n := range nums {
        if candidate1 != nil && *candidate1 == n {
            count1++
        } else if candidate2 != nil && *candidate2 == n {
            count2++
        } else if count1 == 0 {
            candidate1 = &n
            count1 = 1
        } else if count2 == 0 {
            candidate2 = &n

Algorithm

Поиск кандидатов: Пройдите через массив, используя алгоритм Бойера-Мура для поиска двух потенциальных кандидатов, которые могут встречаться более ⌊ n/3 ⌋ раз. Поддерживайте два счётчика и двух кандидатов. Если текущий элемент равен одному из кандидатов, увеличьте соответствующий счётчик. Если счётчик равен нулю, установите текущий элемент как кандидата и установите счётчик в 1. Если текущий элемент не совпадает ни с одним из кандидатов, уменьшите оба счётчика.

Подсчёт голосов: После определения двух кандидатов, пройдите через массив снова, чтобы посчитать фактическое количество появлений каждого кандидата.

Проверка порога: Проверьте, превышает ли количество появлений каждого кандидата порог ⌊ n/3 ⌋. Если да, добавьте кандидата в результат.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.