1287. Element Appearing More Than 25% In Sorted Array

leetcode easy

#array#csharp#easy#hash-table#leetcode#search#sort

Task

Дан массив целых чисел, отсортированный в неубывающем порядке. В этом массиве есть ровно одно число, которое встречается более чем в 25% случаев. Верните это число.

Пример:

Input: arr = [1,2,2,6,6,6,6,7,10]

Output: 6

C# solution

matched/original

using System.Collections.Generic;
public class Solution {
    public int FindSpecialInteger(int[] arr) {
        Dictionary<int, int> counts = new Dictionary<int, int>();
        int target = arr.Length / 4;
        foreach (int num in arr) {
            if (!counts.ContainsKey(num)) {
                counts[num] = 0;
            }
            counts[num]++;
            if (counts[num] > target) {
                return num;
            }
        }
        return -1;
    }
}

C++ solution

auto-draft, review before submit

#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 int FindSpecialInteger(vector<int>& arr) {
        unordered_map<int, int> counts = new unordered_map<int, int>();
        int target = arr.size() / 4;
        foreach (int num in arr) {
            if (!counts.count(num)) {
                counts[num] = 0;
            }
            counts[num]++;
            if (counts[num] > target) {
                return num;
            }
        }
        return -1;
    }
}

Java solution

matched/original

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int findSpecialInteger(int[] arr) {
        Map<Integer, Integer> counts = new HashMap<>();
        int target = arr.length / 4;
        for (int num : arr) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
            if (counts.get(num) > target) {
                return num;
            }
        }
        return -1;
    }
}

JavaScript solution

matched/original

var findSpecialInteger = function(arr) {
    const counts = {};
    const target = arr.length / 4;
    for (const num of arr) {
        counts[num] = (counts[num] || 0) + 1;
        if (counts[num] > target) {
            return num;
        }
    }
    return -1;
};

Python solution

matched/original

from collections import defaultdict

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        counts = defaultdict(int)
        target = len(arr) / 4
        for num in arr:
            counts[num] += 1
            if counts[num] > target:
                return num
        return -1

Explanation

Algorithm

Инициализируйте хеш-таблицу counts и перебирайте каждый элемент в массиве arr, увеличивая counts[num] для каждого элемента num.

Установите target = arr.length / 4.

Перебирайте каждую пару ключ-значение в counts и, если значение > target, верните ключ. Код никогда не достигнет этой точки, так как гарантируется, что ответ существует; верните любое значение.

😎