Први елемент који се јавља к пута у низу


Ниво тешкоће Лако
Често питани у амазонка Пешачење ПаиУ САП Лабс терадата випро Иатра Зохо
Ред Хасх

Дали смо број 'к' и целобројни низ. Проблем „Први елемент који се јавља к пута у низу“ каже да се сазна први елемент у низу који се јавља тачно к пута у низу. Ако у низу нема елемента који се јавља к пута, вратите -1.

Пример

Пронађите елементе распона који недостају

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

Објашњење

У овом примеру постоје два елемента која се јављају к пута. 4 и 2 постоје тачно к број пута, али 4 је прва која се догоди к пута. Дакле, враћамо 4.

Алгоритам

  1. Изјавите а ХасхМап.
  2. Пређите низ.
    • Пребројите и похраните фреквенцију сваког елемента низа на мапу.
  3. Поново пређите низ и проверите да ли је фреквенција сваког елемента низа једнака к.
    • Ако услов задовољава, вратите елемент.

Објашњење

Улазне вредности имамо као цео број поредак и цео број к. Изјава о проблему тражи да се открије први елемент у низу који се јавља тачно к пута. Да бисмо решили овај проблем, користићемо Хасхинг. Хеширање је могући начин на који можемо смањити временску сложеност. То кошта Он) сложеност времена.

Бројићемо и чувати учесталост сваког елемента на нашој мапи. Претпоставимо да елемент долази 3 пута у низ, ми смо његову фреквенцију поставили као 3, заједно са тим елементом. ХасхМап се у ту сврху може користити за чување кључева и вредности. Све елементе чуваћемо као кључеве и њихове фреквенције као вредности у ХасхМап-у. Тада ћемо покренути петљу и прећи низ, одабрати сваки елемент и проверити њихову учесталост. Ако се утврди да је фреквенција било ког елемента једнака к, тада ћемо вратити тај елемент. Будући да обилазимо низ, па ако је елемент пронађен са појавом к пута. Тада ће то дефинитивно бити први елемент са к бројем појављивања.

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

арр [] = {2,4,6,4,2,1,}, к = 2

На мапи ћемо чувати елементе као кључеве и њихове фреквенције као вредности, након што наша мапа има следеће вредности:

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

Проверићемо сваки елемент низа, почев од 0-тог индекса започињемо обилажење низа

и = 0,

ако је фреквенција сваког низа [и] == к:

Фреквенција 2 је 2, што је једнако к, а то је и елемент који долази први са к без појављивања, па враћамо арр [и] и наш излаз би био 2.

У случају да се било која фреквенција елемента не подудара са 'к', тада ћемо вратити -1.

код

Ц ++ код за проналажење првог елемента који се јавља к пута у низу

#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

Јава код за проналажење првог елемента који се јавља к пута у низу

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

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

Сложеност времена

Он) где „Н“ је број елемената у низу. Ево, пошто смо користили хеш-мапу, могли смо да изводимо операције у О (1) времену.

Сложеност простора

Он) где „Н“ је број елемената у низу. У најгорем случају када су сви елементи различити. Морат ћемо похранити свих Н елемената на мапу који ће заузети линеарни простор.