Baş frekansları k-dən böyük və ya bərabər olan ədədlər

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Akkolit Amazon Məlumat dəsti Fourkites Boz Portağal Pinterest Xome
Geyim Sükut Baş nömrəBaxılıb 33

Problem bəyanat

Məsələ “Baş frekansları k-dan böyük və ya bərabər olan ədədlər” sizə n ölçülü bir ədəd və k tam ədədin verildiyini bildirir. İçindəki bütün rəqəmlər sadə rəqəmlərdir. Problem problemi, massivdə ən az k dəfə və massivdə ən çox dəfə görünən rəqəmləri tapmağı xahiş edir.

misal

arr[] = {29, 11, 37, 53, 53, 53, 29, 53, 29, 53}, k = 2
29 and 53

İzahat: 29 və 53 sırasıyla 3 dəfə və 5 dəfə görünür ki, bu da ən azı k dəfə görünmə şərtini təmin edir.

Baş frekansları k-dən böyük və ya bərabər olan ədədləri tapmaq alqoritmi

1. Declare a map and store all the numbers of the array in the map with their frequencies.
2. Traverse the map.
    1. Check if the frequency of each element is at least k or greater than k.
    2. Find if that frequency is a prime number or not.
    3. If the frequency is a prime number then print that key else go for other numbers.

Izahat

Bir sıra tam və k dəyəri vermişik. Verilən bütün rəqəmlər də birincidir, sayın ən azı k dəfə və sıra içərisində hər hansı bir əsas say dəfə görünüb-görünmədiyini öyrənməyimizi xahiş etdik, sonra bu rəqəmi yazdırın. Bunu həll etmək üçün Hashing metod. Biz istifadə edəcəyik xəritə. Bizim vəzifəmiz bir rəqəmin görünüşünü tapmaqdır, yəni hər bir elementin meydana gəlməsini tapmaq məcburiyyətindəyik, bunu həll etmək üçün bir Xəritə istifadə edəcəyik.

Dizini keçib hər elementi və tezliyini xəritədə sayıb saxlayacağıq. Sayı xəritədə yeni bir girişdirsə, xəritədə onun üçün bir yer qoyun və tezliyini 1 kimi qeyd edin. Əgər mövcuddursa, sadəcə tezliyini əldə edin və tezliyini 1 artırın və yenidən həmin tezliyi əlavə edin onun sayı. Bu sayədə hər sayın bütün tezliklərini saya bilərik. İndi hər bir rəqəmin tezliyinin əvvəlcə k dəfə olduğunu və eyni zamanda göründüyü zamanın sadə bir say olub olmadığını yoxlamalıyıq.

Bu vəziyyətdə bir xəritədə hər düyməni keçib tezliyini əldə edəcəyik. Tezliyin əsas rəqəm olub olmadığını yoxlayan bir funksiya yaratdıq. Əsas say üçün 1 olmamalı, həm də özündən başqa bir ədədə bölünməməlidir. Əgər hər hansı bir rəqəmə bölünürsə, yalnış qayıdır. Bölünürsə, o düyməni həmin tezliyin nömrəsi deməkdir və başqa bir sıra üçün davam edin.

 

Baş frekansları k-dən böyük və ya bərabər olan ədədlərPin

 

Kodu

Əsas tezlikləri k-dən böyük və ya bərabər olan nömrələri tapmaq üçün C ++ kodu

#include<iostream>
#include<unordered_map>

using namespace std;

bool checkIfPrime(int n)
{
    if (n <= 1)
        return false;

    for (int i = 2; i < n; i++)
        if (n % i == 0)
            return false;

    return true;
}
void numberWithPrimeFreq(int arr[], int k)
{
    unordered_map<int, int> MAP;

    for (int i = 0; i < 12; i++)
        MAP[arr[i]]++;

    for (auto x : MAP)
    {
        if (checkIfPrime(x.second) && x.second >= k)
            cout << x.first << endl;
    }
}
int main()
{
    int arr[] = { 29,11,37,53,53,53,29,53,29,53 };
    int k = 2;

    numberWithPrimeFreq(arr, k);
    return 0;
}
29
53

Əsas tezlikləri k-dən böyük və ya bərabər olan nömrələri tapmaq üçün Java kodu

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

public class  Frequencies_PrimeNumber
{
  public static void numberWithPrimeFreq(int[] arr, int k)
  {
    Map<Integer, Integer> MAP = new HashMap<>();

    for (int i = 0; i < arr.length; i++)
    {
      int val = arr[i];

      int freq;
      if (MAP.containsKey(val))
      {
        freq = MAP.get(val);
        freq++;
      }
      else
        freq = 1;
      MAP.put(val, freq);
    }
    for (Map.Entry<Integer, Integer> entry :MAP.entrySet())
    {
      int TEMP = entry.getValue();
      if (checkIfPrime(TEMP) && TEMP >= k)
        System.out.println(entry.getKey());
    }
  }
  private static boolean checkIfPrime(int n)
  {
    if ((n > 2 && n % 2 == 0) || n == 1)
      return false;

    for (int i = 2 ; i <n;	i ++)
    {
      if (n % i == 0)
        return false;
    }
    return true;
  }
  public static void main(String[] args)
  {
    int[] arr = { 29,11,37,53,53,53,29,53,29,53 };
    int k = 2;

    numberWithPrimeFreq(arr, k);
  }
}
53
29

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

Burada, k tezlikli n / k elementlərimiz olduğunu düşündüyümüz üçün hər dəfə primallıq yoxlanılacaqdır. Lakin ilk növbədə yoxlama yalnız O (n) vaxt aparır. Burada n tezlikdir. Yəni ən pis halda da bütün alqoritm xətti vaxtda işləyə bilər. O (N) hara "N"  massivdəki elementlərin sayıdır.

Kosmik Mürəkkəblik

Girişin saxlanması üçün lazım olan yer olduğundan, O (N) hara "N"  massivdəki elementlərin sayıdır.

Translate »