პირველი ელემენტი ხდება მასივში k ჯერ


Რთული ტური Easy
ხშირად ეკითხებიან Amazon ლაშქრობა პეუ SAP ლაბორატორიები Teradata Wipro Yatra Zoho
Array Hash

ჩვენ მივეცით რიცხვს "k" და მთელი რიგი. პრობლემა ”პირველი ელემენტი ხდება მასივში k ჯერ” ამბობს მასივის პირველი ელემენტის გასარკვევად, რომელიც ხდება მასივში ზუსტად k ჯერ. თუ მასივში არ არის ელემენტი, რომელიც ხდება k ჯერ, მაშინ დავაბრუნოთ -1.

მაგალითი

დიაპაზონის დაკარგული ელემენტების მოძებნა

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

განმარტება

ამ მაგალითში არსებობს ორი ელემენტი, რომლებიც გვხვდება k ჯერ. 4 და 2 ზუსტად k რამდენჯერმე არსებობს, მაგრამ 4 არის პირველი, რაც ხდება k ჯერ. ასე რომ, ჩვენ დავბრუნდებით 4.

ალგორითმი

  1. გამოაცხადეთ ა HashMap.
  2. მასივის გადაკვეთა.
    • დაითვალეთ და შეინახეთ მასივის თითოეული ელემენტის სიხშირე რუკაზე.
  3. კვლავ გადალახეთ მასივი და შეამოწმეთ, არის თუ არა მასივის თითოეული ელემენტის სიხშირე ტოლი k.
    • თუ პირობა აკმაყოფილებს, მაშინ დააბრუნე ელემენტი.

განმარტება

ჩვენ გვაქვს ჩვენი შეყვანის მნიშვნელობები მთელი რიცხვი მასივი და მთელი k. პრობლემის დებულება ითხოვს მასივის პირველი ელემენტის გარკვევას, რომელიც ხდება ზუსტად k ჯერ. ამ პრობლემის მოსაგვარებლად, ჩვენ ვაპირებთ გამოვიყენოთ ჰაშინგი. გარჩევა არის შესაძლო გზა, რომლის საშუალებითაც შეგვიძლია შევამციროთ ჩვენი დროის სირთულე. Ღირს O (n) დროის სირთულე.

ჩვენ დავათვლით და შევინახავთ თითოეული ელემენტის სიხშირეს ჩვენს რუკაზე. დავუშვათ, რომ მასივში 3-ჯერ მოდის ელემენტი, ჩვენ მის სიხშირეს ვადგენთ 3-ზე, ამ ელემენტთან ერთად. HashMap შეიძლება გამოყენებულ იქნას გასაღებებისა და მნიშვნელობების შესანახად. ჩვენ ვინახავთ HashMap- ში ყველა ელემენტს, როგორც გასაღებებს და მათ სიხშირეებს. შემდეგ ჩვენ გავატარებთ მარყუჟს და გადავკვეთთ მასივს და ავირჩევთ თითოეულ ელემენტს და შეამოწმებთ მათ სიხშირეს. თუ აღმოჩნდა, რომ რომელიმე ელემენტის სიხშირე ტოლია k- ს, მაშინ ჩვენ დავუბრუნებთ ამ ელემენტს. მას შემდეგ, რაც ჩვენ ვაკვირდებით მასივს, ასე რომ, თუ ელემენტი ნაპოვნია კ ჯერზე. მაშინ ის ნამდვილად იქნება პირველი ელემენტი, რომელსაც არ აქვს კ.

განვიხილოთ მაგალითი:

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

ჩვენ შევაგროვებთ ელემენტებს, როგორც გასაღებებს და მათ სიხშირეებს, როგორც მნიშვნელობებს რუქაში, ჩვენი რუქის შენახვის შემდეგ შემდეგ მნიშვნელობებს:

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

ჩვენ შეამოწმებთ მასივის თითოეულ ელემენტს, 0-ე ინდექსიდან დავიწყებთ მასივის გადახედვას

მე = 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

ჯავის კოდი მასივში 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 (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა. აქ, ვინაიდან ჩვენ გამოვიყენეთ ჰეშმაპი, ჩვენ შევძელით ოპერაციების შესრულება O (1) დროში.

სივრცის სირთულე

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა. უარეს შემთხვევაში, როდესაც ყველა ელემენტი მკაფიოა. ჩვენ მოგვიწევს ყველა N ელემენტის შენახვა რუქაში, რომელიც წრფივ ადგილს დაიკავებს.