Анхны давтамжтай тоо k-ээс их эсвэл тэнцүү


Хэцүү байдлын түвшин Easy
Байнга асуудаг Accolite Амазоны Factset Фуркайт Саарал улбар шар Pinterest Xome
Array Хаш Анхны тоо

Асуудлын мэдэгдэл

“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 удаа гарч ирэх эсэхийг олж мэдээд дараа нь тэр тоог хэвлээрэй гэж хүссэн. Үүнийг шийдэхийн тулд бид Хаширч байна арга. Бид ашиглах болно газрын зураг. Бидний даалгавар бол тооны харагдах байдлыг олох явдал бөгөөд энэ нь элемент бүрийн илрэлийг олох ёстой гэсэн үг бөгөөд үүнийг шийдвэрлэхийн тулд бид Газрын зургийг ашиглах болно.

Бид массивыг дайран өнгөрч, элемент бүр болон давтамжийг газрын зураг дээр тоолж хадгална. Хэрэв энэ тоо нь газрын зурагт шинээр оруулсан бол газрын зураг дээр байрлуулж, давтамжаа 1 гэж тэмдэглэ. Хэрэв аль хэдийн байгаа бол түүний давтамжийг авч, давтамжаа 1-ээр нэмэгдүүлж, тухайн давтамжийг дахин оруулна уу түүний дугаар. Ийм байдлаар бид дугаар бүрийн бүх давтамжийг тоолж чадна. Одоо бид тоо бүрийн давтамж, k тоогоор бас хэдэн удаа гарч байгааг мөн анхны тоо байх ёстой эсэхийг шалгах хэрэгтэй.

Энэ тохиолдолд бид газрын зураг дээрх түлхүүр бүрийг тойрон давтаж, давтамжийг нь олж авах болно. Бид давтамж нь анхны тоо байгаа эсэхийг шалгадаг функц хийсэн. Энгийн тооны хувьд энэ нь 1 байх ёсгүй, өөрөөсөө өөр тоонд хуваагдах ёсгүй. Хэрэв энэ нь аль ч тоонд хуваагдах юм бол худал утгыг буцаана. Хэрэв хуваагдвал тухайн товчлуурыг тухайн давтамжийн тоог хэвлээд дараа нь өөр тоог үргэлжлүүлээрэй.

 

Анхны давтамжтай тоо k-ээс их эсвэл тэнцүү

 

код

Анхны давтамжтай k-ээс их буюу тэнцүү тоонуудыг олох C ++ код

#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

Анхны давтамжтай k-ээс их буюу тэнцүү тоог олох Java код

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

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

Энд k давтамжтай n / k элементүүд байгаа тул давуу эрх бүрийг шалгаж байх болно гэж үзье. Гэхдээ давуу эрх шалгах нь зөвхөн O (n) цаг хугацаа шаарддаг. Энд n нь давтамж юм. Тиймээс хамгийн муу тохиолдолд ч гэсэн алгоритм бүхэлдээ шугаман хугацаанд ажиллах боломжтой. O (N) хаана "N"  массив дахь элементүүдийн тоо юм.

Сансрын нарийн төвөгтэй байдал

Оролтыг хадгалах зай шаардагддаг тул O (N) хаана "N"  массив дахь элементүүдийн тоо юм.