Bir Array Ən Tez-tez Element

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çiy kərpic Amazon Məlumat dəsti Fourkites Infosys MAQ
Geyim Sükut Hashing çeşidləyiciBaxılıb 50

Sizə verilir array tam ədədi. Problem ifadəsində deyilir ki, bir massivdə mövcud olan ən çox elementi tapmaq lazımdır. Maksimum dəfə baş verən birdən çox dəyər varsa, bunlardan hər hansı birini çap etməliyik.

misal

Input

[1, 4,5,3,1,4,16]

Buraxılış

Ən Tez-tez Element: 1

Izahat

Burada 1 3 dəfə gəlir (bir sıra içərisində ən çox görülən element)

Input

[23,12,12,34,23,23]

Buraxılış

Ən Tez-tez Element: 23

Izahat

Burada 23 3 dəfə gəlir (bir sıra içərisində ən çox görülən element)

Alqoritm

  1. Xəritə elan et.
  2. Bir massivin hər bir elementinin tezliyini hesablayın və xəritədə saxlayın.
  3. MaxCount'u 0 olaraq təyin edin və Tamsayı minimum dəyəri ilə nəticələnin.
  4. Xəritədən keçin və yoxlayın:
    1. MaxCount
      1. Nəticəni həmin element elementinə qoyun
      2. Bu elementin tezliyinə maxCount qoyun

Bir Dizidəki Ən Tez-tez Element üçün İzahat

Burada verilən sual, bir massivdə mövcud olan ən çox rast gəlinən elementi tapmaqdır. Bundan əlavə, maksimum dəfə baş verən birdən çox dəyər varsa, hər hansı birini çap etməkdə sərbəst olduğumuz bildirilir. Kod bir element kimi açar və dəyərləri olan xəritədən keçir və bu vəziyyət baş verərsə onların tezliyi, onda ilk maksimum tez-tez çıxacaq. Arqumentləri bir sıra və sıra uzunluğu kimi qəbul edən getMostFrequent funksiyasını təyin edəcəyik. Buradakı ilk şey, serialı keçmək və hər bir sıra elementinin tezliyini saxlamaq və saymaq və hər bir element elementinin tezliyini artırmağa davam etməkdir.

Bunun üçün maxCount və nəticə olaraq iki dəyər istifadə edəcəyik. MaxCount dəyərini 0-a başladın və nəticəni Minimum Tamsayıya gətirin. Xəritədən keçib maxCount-un bir elementin tezliyindən az olub olmadığını yoxlayacağıq, doğrusu tapılsa, maxCount dəyərini elementin tezliyinə qoyacağıq və nəticəni həmin elementə verəcəyik.

Bir nümunəni nəzərdən keçirək:

misal

arr = {2, 5, 2, 3, 3, 2, 1}

Dizini keçəcəyik, hər elementin tezliklərini sayacağıq və saxlayacağıq, keçdikdən sonra xəritəmiz belə olacaq.

myMap={1:1, 2:3, 3:2, 5:1}

Xəritədən keçib hər bir elementi götürəcəyik və maxCount-dan çox olduqda onların tezliyini yoxlayacağıq,

maxCount = 0, nəticə = Tamsayı.MIN_VALUE

  • dəyər = 1, tezlik = 1

maxCount <value.second doğrudursa, maxCount və nəticə dəyərini yeniləyin

nəticə = dəyər.birincisi, maxCount = dəyər. ikinci;

nəticə = 1, maxCount = 1

  • dəyər = 2, tezlik = 3

maxCount <value.second doğrudursa, maxCount və nəticə dəyərini yeniləyin

nəticə = dəyər.birincisi, maxCount = dəyər. ikinci;

nəticə = 2, maxCount = 3

  • dəyər = 3 tez = 2

maxCount <value.second yanlışdırsa, heç nə etmir.

  • dəyər = 5 tez = 1

maxCount <value.second yanlışdırsa.

Xəritənin bütün dəyərlərini keçdik və nəticədə lazımi nəticəni əldə etdik və nəticəni qaytaracağıq.

Nəticə = 2

Bir Array Ən Tez-tez ElementPin

Həyata keçirilməsi

Dizidəki Ən Tez-tez Elementlər üçün C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;

int getMostFrequent(int arr[], int n)
{
    unordered_map<int, int> myMap;
    for (int i = 0; i < n; i++)
        myMap[arr[i]]++;

    int maxCount = 0, result = INT_MIN;
    for (auto value : myMap)
    {
        if (maxCount < value.second)
        {
            result = value.first;
            maxCount = value.second;
        }
    }
    return result;
}
int main()
{
    int arr[] = { 2, 5, 2, 3, 3, 2, 1 };
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getMostFrequent(arr, n);
    return 0;
}
2

Dizidəki Ən Tez-tez Elementlər üçün Java Proqramı

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

class mostFrequentElement
{
    public static int getMostFrequent(int arr[], int n)
    {
        Map<Integer, Integer> myMap =new HashMap<Integer, Integer>();

        for(int i = 0; i < n; i++)
        {
            if(myMap.containsKey(arr[i]))
            {
                myMap.put(arr[i], myMap.get(arr[i])+1);
            }
            else
            {
                myMap.put(arr[i], 1);
            }
        }
        int maxCount = 0, result= Integer.MIN_VALUE ;
        for(Entry<Integer, Integer> val : myMap.entrySet())
        {
            if (maxCount < val.getValue())
            {
                result = val.getKey();
                maxCount = val.getValue();
            }
        }
        return result;
    }
    public static void main (String[] args)
    {
        int arr[] = { 2, 5, 2, 3, 3, 2, 1 };
        int n = arr.length;
        System.out.println(getMostFrequent(arr, n));
    }
} 
2

Bir Dizidəki Ən Tez-tez Element üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (n) hara "N" massivdəki elementlərin sayıdır.

Kosmik Mürəkkəblik

O (n) hara "N" massivdəki elementlərin sayıdır.

References

Translate »