በአንድ ድርድር ውስጥ k ጊዜ የሚከሰት የመጀመሪያ አካል  


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን ረጅም መንገድ ተንሸራሸረ PayU የ SAP ላብራቶሪዎች ተራዳታ Wipro Yatra ቮሆ
ሰልፍ ሃሽ

የቁጥር ‹ኬ› እና የኢቲጀር ድርድር ሰጥተናል ፡፡ ችግሩ “በአንድ ድርድር ውስጥ k ጊዜ የሚከሰት የመጀመሪያው ንጥረ ነገር” በአንድ ድርድር ውስጥ በትክክል k ጊዜ የሚከሰተውን በድርድር ውስጥ የመጀመሪያውን ንጥረ ነገር ለማወቅ ይናገራል። በድርድሩ ውስጥ k ንጥረ ነገሮች የሚከሰቱ ንጥረ ነገሮች ከሌሉ ከዚያ ይመለሱ -1.

ለምሳሌ  

የአንድ ክልል የጎደሉ አባሎችን ያግኙጭንቅላታም መያያዣ መርፌ

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

ማስረጃ

በዚህ ምሳሌ ውስጥ k ጊዜያት የሚከሰቱ ሁለት አካላት አሉ ፡፡ 4 እና 2 በትክክል የ k ቁጥር ብዛት ይኖራሉ ፣ ግን 4 ጊዜ የሚሆነው የመጀመሪያው ነው k ጊዜያት ፡፡ ስለዚህ 4 እንመለሳለን ፡፡

አልጎሪዝም  

  1. ያውጅ ሀ ሃሽ ማፕ.
  2. ድርድርን ያቋርጡ።
    • የእያንዲንደ የሰሌዳውን ንጥረ ነገር ድግግሞሽ በካርታው ውስጥ ቆጥረው ያከማቹ።
  3. እንደገና ድርድርን ያቋርጡ እና እያንዳንዱ የድርጅት ንጥረ ነገር ድግግሞሽ ከ k ጋር እኩል መሆኑን ያረጋግጡ።
    • ሁኔታው የሚያረካ ከሆነ ኤለመንቱን ይመልሱ።

ማስረጃ

እንደ እኛ የግብዓት እሴቶቻችን አሉን ኢንቲጀር ደርድር እና ኢንቲጀር ኪ. የችግሩ መግለጫ በትክክል k ጊዜያት በሚከሰት ድርድር ውስጥ የመጀመሪያውን ንጥረ ነገር ለማወቅ ይጠይቃል። ይህንን ችግር ለመፍታት እኛ ልንጠቀምበት ነው ሃምሽንግ. የጊዜ ውስብስብነታችንን ለመቀነስ ሃሽንግ የሚቻልበት መንገድ ነው ፡፡ ያስከፍላል ሆይ (n) የጊዜ ውስብስብነት.

የእያንዳንዱን ንጥረ ነገር ድግግሞሽ በካርታችን ውስጥ እንቆጥረዋለን እናከማቸዋለን ፡፡ አንድ ንጥረ ነገር በአንድ ድርድር ውስጥ 3 ጊዜ ይመጣል እንበል ፣ ከዚያ ኤለመንት ጋር ድግግሞሹን እንደ 3 እናደርጋለን። ሃሽማፕ ቁልፎችን እና እሴቶችን ለማከማቸት ለዚህ ዓላማ ሊያገለግል ይችላል ፡፡ ሁሉንም ንጥረ ነገሮች እንደ ቁልፎች እና የእነሱ ድግግሞሾች እንደ እሴቶች በሃሽ ማፕ ውስጥ እናከማቻቸዋለን። ከዚያ እኛ አንድ ዙር እንሠራለን እና አንድ ድርድርን እናቋርጣለን እና እያንዳንዱን ንጥረ ነገር እንመርጣለን እና ድግግሞሾቻቸውን እንፈትሻለን ፡፡ የማንኛውንም ንጥረ ነገር ድግግሞሽ ከ 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 no of the ክስተቶች ፣ ስለዚህ እኛ ጉዳዩን እንመልሳለን እናም ውጤታችን 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 ጊዜ የሚከሰት የመጀመሪያ አካል ለማግኘት የጃቫ ኮድ

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

ውስብስብነት ትንተና  

የጊዜ ውስብስብነት

ሆይ (n) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው። እዚህ ፣ ሀሽፕ ተጠቅመናል ስለሆነም በ (1) ጊዜ ውስጥ ክዋኔዎችን ማከናወን ችለናል ፡፡

ተመልከት
የተሰጠ የተቀናጀ ድርድር ሁሉንም የተለዩ ንጥረ ነገሮችን ያትሙ

የቦታ ውስብስብነት

ሆይ (n) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው። ሁሉም ንጥረ ነገሮች የተለዩ ሲሆኑ በጣም በከፋ ሁኔታ ውስጥ ፡፡ መስመራዊ ቦታን የሚወስደውን ሁሉንም የኤን አባሎችን በካርታው ውስጥ ማከማቸት አለብን ፡፡