Першы элемент, які сустракаецца k разоў у масіве  


Узровень складанасці Лёгка
Часта пытаюцца ў амазонка Паход PayU Лабараторыі SAP Teradata Wipro яйкі Zoho
масіў гашыш

Мы далі лік "k" і цэлы лік. Задача «Першы элемент, які сустракаецца ў масіве k разоў», кажа высветліць першы элемент у масіве, які сустракаецца роўна k разоў у масіве. Калі ў масіве няма элемента, які сустракаецца k разоў, вярніце -1.

Прыклад  

Знайдзіце адсутнічаюць элементы дыяпазонуPin

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 разоў. Тады, безумоўна, гэта будзе першы элемент, у якога няма выпадкаў.

Глядзіце таксама
Знайдзіце рашэнне розніцы Leetcode

Давайце разгледзім прыклад:

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

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

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

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

i = 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 элементаў, якія зоймуць лінейную прастору.