Ададҳое, ки басомади аввалашон аз k калон ё ба он баробаранд


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Акколити Amazon Маълумот Фуркайтҳо Грей норанҷӣ ба дӯстат 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 маротиба ва инчунин ягон маротиба шумораи аввалин дар массив пайдо шавад, пас ин рақамро чоп кунед. Барои ҳалли ин, мо аз Хашм усул. Мо истифода мебарем харита. Вазифаи мо пайдо кардани намуди рақам аст, яъне маънои пайдоиши ҳар як унсурро пайдо кардан лозим аст, то ин ки Map -ро истифода барем.

Мо массивро тай карда, ҳар як элемент ва басомади онро ҳисоб карда захира мекунем. Агар рақам вуруди нав дар харита бошад, пас барои он дар харита ҷойгоҳе гузоред ва басомади онро ҳамчун 1 қайд кунед. Агар он аллакай мавҷуд бошад, пас басомади онро дарёфт кунед ва басомади онро 1 афзоиш диҳед ва дубора ин басомадро илова кунед шумораи он. Бо ин роҳ, мо метавонем ҳамаи басомадҳои ҳар як рақамро ҳисоб кунем. Ҳоло мо бояд санҷем, ки оё басомади ҳар як рақам, аввалан k маротиба вуҷуд дорад ва инчунин шумораи пайдоиши он бояд адади асосӣ бошад.

Дар ин ҳолат, мо ҳар як калидро дар харита убур намуда, басомади онро мегирем. Мо вазифае сохтем, ки месанҷад, ки оё басомад адади асосӣ аст ё не. Барои адади аввал, он набояд 1 бошад ва инчунин набояд ба рақами дигаре аз худ тақсим карда шавад. Агар он ба ягон рақам тақсим карда шавад, пас баргаштанро баргардонед. Агар он тақсимшаванда бошад, он калидро бо миқдори басомади мазкур чоп кунед ва барои рақами дигар идома диҳед.

 

Ададҳое, ки басомади аввалашон аз k калон ё ба он баробаранд

 

рамз

Коди C ++ барои ёфтани рақамҳое, ки басомади онҳо аз 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 басомад аст. Пас, ҳатто дар ҳолати бадтарин, тамоми алгоритм метавонад дар вақти хаттӣ кор кунад. О (Н) ки дар "N"  шумораи унсурҳои массив аст.

Мураккабии фазо

Азбаски барои нигоҳ доштани вуруд фазо лозим аст, О (Н) ки дар "N"  шумораи унсурҳои массив аст.