229. Majority Element II

LeetCode medium original: C# #array #csharp #leetcode #medium #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 целых чисел размера n, find все elementы, которые встречаются более ⌊ n/3 ⌋ раз.

Ví dụ

Input: nums = [3,2,3]

Output: [3]

C# lời giải

đã khớp/gố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++ 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:
    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 lời giải

đã khớp/gốc

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 lời giải

đã khớp/gốc

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 lời giải

đã khớp/gốc

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 lời giải

đã khớp/gốc

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

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

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

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

😎

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.