Унсури аввал, ки дар массив k маротиба рух медиҳад


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Amazon саёҳат кардан PayU Лабораторияҳои SAP Терадата Wipro Яра Зохо
тартиботи ҳарбӣ Хаш

Мо рақами 'k' ва массиви бутун додем. Масъалаи "Элементи аввал, ки дар массив k маротиба рух медиҳад" мегӯяд, ки унсури аввалини массив, ки дақиқан k маротиба дар массив рух медиҳад. Агар дар массив ягон элементе вуҷуд надошта бошад, ки k маротиба ба амал ояд, пас -1 бармегардем.

мисол

Унсурҳои гумшудаи диапазонро ёбед

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

Шарҳ

Дар ин мисол, ду унсур мавҷуданд, ки k маротиба рух медиҳанд. 4 ва 2 дақиқан k маротиба вуҷуд доранд, аммо 4 аввалинест, ки k маротиба рух медиҳад. Пас, мо бармегардем 4.

Алгоритм

  1. Эълом кунед a HashMap.
  2. Массивро тай кунед.
    • Басомади ҳар як унсури массивро ҳисоб кунед ва дар харита нигоҳ доред.
  3. Боз массивро тай кунед ва басомади ҳар як унсури массивро ба 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 сар карда, мо ба убур кардани массив оғоз мекунем

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 элементро дар харита нигоҳ дорем, ки фазои хатиро мегирад.