Первый элемент, встречающийся в массиве k раз


Сложный уровень Легко
Часто спрашивают в Амазонка Поход PayU SAP Labs Teradata Wipro ятра Zoho
массив Hash

Мы дали число «k» и целочисленный массив. Задача «Первый элемент, встречающийся k раз в массиве» говорит о том, чтобы найти первый элемент в массиве, который встречается в массиве ровно k раз. Если в массиве нет элемента, который встречается k раз, верните -1.

Пример

Найти недостающие элементы диапазона

Arr[]={1,4,5,2,4,2,7},  k=2
4

объяснение

В этом примере два элемента встречаются k раз. 4 и 2 существуют ровно k раз, но 4 - первое, что встречается k раз. Итак, возвращаем 4.

Алгоритм

  1. Объявить HashMap.
  2. Пройдите по массиву.
    • Подсчитайте и сохраните частоту каждого элемента массива на карте.
  3. Снова пройдитесь по массиву и проверьте, равна ли частота каждого элемента массива k.
    • Если условие удовлетворяется, вернуть элемент.

объяснение

У нас есть входные значения как целое массив и целое число k. В постановке задачи предлагается найти первый элемент массива, который встречается ровно k раз. Чтобы решить эту проблему, мы будем использовать хеширования. Хеширование - это возможный способ уменьшить нашу временную сложность. Это стоит О (п) сложность времени

Мы будем считать и сохранять частоту каждого элемента на нашей карте. Предположим, что элемент встречается 3 раза в массиве, мы установили его частоту как 3 вместе с этим элементом. HashMap можно использовать для этой цели для хранения ключей и значений. Мы будем хранить все элементы как ключи, а их частоты как значения в HashMap. Затем мы запустим цикл и проходим по массиву, выбираем каждый элемент и проверяем их частоту. Если частота какого-либо элемента окажется равной k, мы вернем этот элемент. Поскольку мы проходим по массиву, значит, если элемент найден с вхождением k раз. Тогда определенно это будет первый элемент, у которого не было k вхождений.

Рассмотрим пример:

arr [] = {2,4,6,4,2,1,}, k = 2

Мы будем хранить элементы как ключи, а их частоты как значения в карте, после сохранения наша карта будет иметь следующие значения:

myMap={1:1, 2:2, 4:2, 6:1};

Мы проверим каждый элемент массива, начиная с 0-го индекса начнем обход массива

я = 0,

если частота каждого массива [i] == k:

Частота 2 равна 2, что равно k, а также для элемента, который идет первым с k не вхождениями, поэтому мы возвращаем arr [i], и наш результат будет 2.

В случае, если частота какого-либо элемента не будет соответствовать «k», мы вернем -1.

Код:

Код C ++ для поиска первого элемента, встречающегося k раз в массиве

#include<iostream>
#include <unordered_map>

using namespace std;

int firstElement(int arr[], int n, int k)
{
    unordered_map<int, int> freqMap;

    for (int i=0; i<n; i++)
        freqMap[arr[i]]++;

    for (int i=0; i<n; i++)
        if (freqMap[arr[i]] == k)
            return arr[i];

    return -1;
}
int main()
{
    int arr[] = {2,4,6,4,2,1,6};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << firstElement(arr, n, k);
    return 0;
}
2

Код Java для поиска первого элемента, встречающегося k раз в массиве

import java.util.HashMap;

class firstKOccuringElement
{
    public static int getFirstElement(int arr[], int n, int k)
    {
        HashMap<Integer, Integer> freqMap = new HashMap<>();
        for (int i = 0; i < n; i++)
        {
            int a = 0;
            if(freqMap.containsKey(arr[i]))
            {
                freqMap.put(arr[i], freqMap.get(arr[i])+1);
            }
            else
            {
                freqMap.put(arr[i], 1);
            }
        }
        for (int i = 0; i < n; i++)
        {
            if (freqMap.get(arr[i]) == k)
            {
                return arr[i];
            }
        }
        return -1;
    }
    public static void main(String[] args)
    {
        int arr[] = {2,4,6,4,2,1,6};
        int n = arr.length;
        int k = 2;
        System.out.println(getFirstElement(arr, n, k));
    }
}
2

Анализ сложности

Сложность времени

О (п) в котором «Н» - количество элементов в массиве. Здесь, поскольку мы использовали хэш-карту, мы могли выполнять операции за время O (1).

Космическая сложность

О (п) в котором «Н» - количество элементов в массиве. В худшем случае, когда все элементы различны. Нам нужно будет сохранить все N элементов на карте, которая займет линейное пространство.