أول عنصر يحدث ك مرات في مصفوفة  


مستوى الصعوبة سهل
كثيرا ما يطلب في أمازون رفع PayU مختبرات SAP مقاومه ويبرو ياترا زوهو
مجموعة مزيج

لقد قدمنا ​​عددًا 'k' ومصفوفة عدد صحيح. تقول مشكلة "أول عنصر يحدث k مرة في المصفوفة" لمعرفة العنصر الأول في المصفوفة والذي يحدث بالضبط k مرة في المصفوفة. إذا لم يكن هناك عنصر في المصفوفة يحدث k مرة ، فسيتم إرجاع -1.

مثال  

البحث عن العناصر المفقودة في النطاقدبوس

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

تفسير

في هذا المثال ، هناك عنصران يحدثان ك مرة. 4 و 2 موجودان بالضبط k عدد المرات ، لكن 4 هو الأول الذي يحدث k مرة. لذا نعود 4.

خوارزمية  

  1. تعلن أ خريطة التجزئة.
  2. اجتياز المصفوفة.
    • قم بحساب وتخزين تكرار كل عنصر من عناصر المصفوفة في الخريطة.
  3. اجتياز المصفوفة مرة أخرى وتحقق مما إذا كان تردد كل عنصر من عناصر المصفوفة يساوي k.
    • إذا استوفى الشرط ، فأعد العنصر.

تفسير

لدينا قيم المدخلات لدينا عدد صحيح مجموعة وعدد صحيح ك. تطلب تعليمة المشكلة معرفة العنصر الأول في المصفوفة التي تحدث بالضبط k مرة. لحل هذه المشكلة ، سنستخدم تجزئة. التجزئة هي الطريقة الممكنة التي يمكننا من خلالها تقليل تعقيد وقتنا. يكلف O (ن) تعقيد الوقت.

سنقوم بحساب وتخزين وتيرة كل عنصر في خريطتنا. لنفترض أن عنصرًا يأتي 3 مرات في مصفوفة ، قمنا بتعيين تردده على 3 ، جنبًا إلى جنب مع هذا العنصر. يمكن استخدام HashMap لهذا الغرض لتخزين المفاتيح والقيم. سنقوم بتخزين جميع العناصر كمفاتيح وتردداتها كقيم في HashMap. ثم سنقوم بتشغيل حلقة ونقطع مصفوفة ونختار كل عنصر ونتحقق من ترددها. إذا وجد أن تردد أي عنصر يساوي k ، فسنقوم بإرجاع هذا العنصر. نظرًا لأننا نجتاز المصفوفة ، لذلك إذا تم العثور على العنصر مع التكرار k مرة. ثم بالتأكيد سيكون العنصر الأول الذي لا يحتوي على عدد مرات حدوث.

انظر أيضا
أوجد حل Leetcode الاختلاف

دعنا نأخذ مثالا:

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

سنقوم بتخزين العناصر كمفاتيح وتردداتها كقيم في الخريطة ، بعد تخزين خريطتنا سيكون لها القيم التالية:

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

سوف نتحقق من كل عنصر من عناصر المصفوفة ، بدءًا من الفهرس 0 سنبدأ في اجتياز المصفوفة

أنا = 0 ،

إذا كان تكرار كل مجموعة [i] == k:

تردد 2 هو 2 ، وهو ما يساوي k كما أنه العنصر الذي يأتي أولاً مع k no من التكرارات ، لذلك نعيد 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 (ن) أين "ن" هو عدد العناصر في المصفوفة. هنا ، نظرًا لأننا استخدمنا علامة التجزئة ، فقد تمكنا من إجراء العمليات في وقت O (1).

انظر أيضا
طباعة جميع العناصر المميزة لمصفوفة عدد صحيح معين

تعقيد الفضاء

O (ن) أين "ن" هو عدد العناصر في المصفوفة. في أسوأ الأحوال عندما تكون جميع العناصر متميزة. سيتعين علينا تخزين جميع العناصر N في الخريطة والتي ستأخذ مساحة خطية.