Числа з простими частотами, більшими або рівними k


Рівень складності Легко
Часто запитують у Accolite Амазонка Факти Фуркіти GreyOrange Пінтерест Xome
масив Мішанина Просте число

Постановка проблеми

У задачі “Числа з простими частотами, більшими або рівними k” зазначено, що вам надано масив цілих чисел розміром n та цілим числом k. Всі числа всередині нього є простими числами. Постановка задачі вимагає з’ясувати числа, які з’являються в масиві принаймні k разів і просту кількість разів у масиві.

Приклад

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

Пояснення: 29 та 53 з’являються відповідно 3 рази та 5 разів, що також задовольняє умові з’являтися принаймні k разів.

Алгоритм пошуку чисел із простими частотами, більшими або рівними k

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.

Пояснення

Ми дали масив цілих чисел і значення k. Всі наведені числа також є основними, ми попросили з’ясувати, чи з’являється це число принаймні k разів, а також будь-яке просте число разів у масиві, а потім надрукувати це число. Для вирішення цього питання ми будемо використовувати Хешування метод. Ми будемо використовувати a карта. Наше завдання - знайти вигляд числа, це означає, що ми повинні знайти появу кожного елемента, для вирішення цього питання ми збираємось використовувати Карту.

Ми перейдемо масив і підрахуємо та збережемо кожен елемент та його частоту на карті. Якщо число є новим записом на карті, то зробіть для нього місце на карті та позначте його частоту як 1. Якщо воно вже існує, просто отримайте його частоту та збільште частоту на 1 і знову вставте цю частоту разом з його номер. Таким чином, ми можемо порахувати всі частоти кожного числа. Тепер нам потрібно перевірити, чи частота кожного числа, по-перше, існує k кількість разів, а також кількість разів, що з'являються, має бути простим числом.

У цьому випадку ми будемо обходити кожну клавішу на карті та отримувати її частоту. Ми створили функцію, яка перевіряє, чи є частота простим числом чи ні. Для простого числа воно не повинно бути 1, а також воно не повинно ділитися на інше число, ніж саме воно. Якщо воно ділиться на будь-яке число, поверніть значення false. Якщо він ділиться, тоді надрукуйте цей ключ, що означає номер цієї частоти, і продовжуйте далі для іншого числа.

 

Числа з простими частотами, більшими або рівними k

 

код

Код С ++ для пошуку чисел із простими частотами, більшими або рівними k

#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

Код Java для пошуку чисел із простими частотами, більшими або рівними k

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

Аналіз складності

Складність часу

Тут розглянемо, що у нас є n / k елементів з частотою k, тому кожен раз перевірятиметься первинність. Але перевірка простоти займає лише O (n) час. Тут n - частота. Тож навіть у гіршому випадку весь алгоритм може працювати в лінійний час. O (N) де "N"  - кількість елементів у масиві.

Складність простору

Через місце, необхідне для зберігання вхідних даних, O (N) де "N"  - кількість елементів у масиві.