Массивде k жолу пайда болгон биринчи элемент  


Кыйынчылык деңгээли жеңил
Көп суралган Amazon селсаяктоо PayU SAP Labs Терадата Wipro Yatra Zoho
согуштук тизме таштанды

Биз 'k' санын жана бүтүндөй массивди бердик. Массивде "массивде k жолу пайда болгон биринчи элемент" маселеси массивде массивде так k жолу кайталанган биринчи элементти табууга мүмкүндүк берет. Эгерде массивде k жолу пайда болгон эч кандай элемент жок болсо, анда -1ди кайтарыңыз.

мисал  

Диапазондун жок элементтерин табуутөөнөч

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

түшүндүрүү

Бул мисалда k жолу пайда болгон эки элемент бар. 4 жана 2 так k жолу бар, бирок 4 биринчи жолу k жолу болот. Ошентип, биз 4 кайтып.

Algorithm  

  1. Декларация a HashMap.
  2. Массивди айланып өтүңүз.
    • Массивдин ар бир элементинин жыштыгын санап, картага сактаңыз.
  3. Кайра массивди айланып өтүп, массивдин ар бир элементинин ж-га барабар экендигин текшериңиз.
    • Эгер шарт канааттандырылса, анда элементти кайтарыңыз.

түшүндүрүү

Биздин киргизүү баалуулуктарыбыз бар бүтүн согуштук тизме жана бүтүн k. Маселе коюлушу массивдеги биринчи элементти так k жолу кайталангандыгын табууну сурайт. Бул көйгөйдү чечүү үчүн биз колдонобуз Hashing. Хэшинг - бул убакыттын татаалдыгын азайтуучу ыкма. Бул чыгымдарды талап кылат O (N) убакыттын татаалдыгы.

Биз ар бир элементтин жыштыгын санап, картабызга сактайбыз. Массивде бир элемент 3 жолу келет дейли, анын жыштыгын ошол элемент менен катар 3 деп койдук. HashMap бул максатта ачкычтарды жана баалуулуктарды сактоо үчүн колдонсо болот. Бардык элементтерди ачкыч катары, ал эми алардын жыштыктарын HashMap файлында баалуулук катары сактайбыз. Андан кийин циклди иштетип, массивди тандап, ар бир элементин тандап, алардын жыштыгын текшеребиз. Эгерде кандайдыр бир элементтин жыштыгы kге барабар деп табылса, анда биз ошол элементти кайтарып беребиз. Биз массивди аралап жүргөндүктөн, эгер элемент пайда болушу менен k жолу табылса. Ошондо, албетте, ал эч кандай пайда болбогон биринчи элемент болот.

ошондой эле
Айрым коддун чечимин табыңыз

Келгиле, бир мисал карап көрөлү:

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 элементтери менен келип чыгат, ошондуктан биз [i] arrusту кайтарабыз жана биздин натыйжабыз 2 болот.

Эгерде кандайдыр бир элементтин жыштыгы 'k' менен дал келбесе, анда биз -1 кайтып келебиз.

коду  

Массивде k жолу пайда болгон биринчи элементти табуу үчүн C ++ коду

#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

Массивде k жолу болгон Биринчи элементти табуу үчүн Java коду

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 (N) кайда "N" массивдеги элементтердин саны. Бул жерде, биз hashmap колдонгонубуз үчүн, O (1) убакыттын ичинде операцияларды жасай алдык.

ошондой эле
Берилген бүтүн массивдин бардык айырмаланган элементтерин басып чыгарыңыз

Космостун татаалдыгы

O (N) кайда "N" массивдеги элементтердин саны. Эң начар учурда, бардык элементтер бири-биринен айырмаланат. Бардык N элементтерди картага сактоо керек, ал сызыктуу орун ээлейт.