Массивт k удаа тохиолдох эхний элемент  


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны явган аялал PayU SAP лабораторууд Teradata Випро фирмийн Ятра Zoho
Array Хаш

Бид '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. Асуудлын шийдэл нь массивын эхний элементийг яг k удаа тохиолдохыг олж мэдэхийг хүсдэг. Энэ асуудлыг шийдэхийн тулд бид ашиглах болно Хаширч байна. Hashing бол бидний цаг хугацааны нарийн төвөгтэй байдлыг багасгах боломжтой арга юм. Энэ зардал O (N) цаг хугацааны нарийн төвөгтэй байдал.

Бид элемент бүрийн давтамжийг газрын зураг дээрээ тоолж хадгалах болно. Массивт нэг элемент 3 удаа ирлээ гэж үзвэл бид түүний давтамжийг 3 гэж тогтоож, тухайн элементийн хамт орууллаа. HashMap-ийг энэ зорилгоор түлхүүрүүд болон утгуудыг хадгалахад ашиглаж болно. Бид бүх элементүүдийг түлхүүр болгон, давтамжуудыг нь HashMap дээр утга болгон хадгалах болно. Дараа нь бид гогцоо ажиллуулж, массивыг дайрч, элемент бүрийг сонгож, тэдгээрийн давтамжийг шалгана. Хэрэв ямар нэг элементийн давтамж k-тэй тэнцүү болохыг олж мэдвэл бид тэр элементийг буцааж өгөх болно. Бид массивыг дайрч байгаа тул элемент тохиолдох тохиолдолд 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 буцаана.

код  

Массивт 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 элементүүдийг газрын зурагт хадгалах ёстой бөгөөд энэ нь шугаман зай эзэлнэ.