Пронајдете ги првите три во низа


Ниво на тешкотија Лесно
Често прашувано во MAQ o9 решенија Випро
Низа Хаш

Проблемот „Пронајди ги трите најдобри повторени во низата“ вели дека ти е даден низа на n броеви со некои повторени броеви во него. Ваша задача е да ги дознаете топ 3 повторените броеви во низата.

пример

Пронајдете ги првите три во низа

[1,3,4,6,7,2,1,6,3,10,5,7]
1 3 6

Објаснување

Тука 1,3 и 6 се повторуваат двапати.

[2,4,2,1,5,6,8,5,3,9,0,1]
1 2 5

Објаснување

Тука 1,2 и 5 се повторуваат двапати.

Алгоритам за наоѓање на првите три повторувани елементи

  1. Прогласи го мапа и класата дефинирана од корисникот наречена Пар.
  2. Врати се ако не постојат најмалку три вредности.
  3. Пребројте ги и зачувајте ги фреквенциите на секој елемент од влезот низа и ставете го на картата.
  4. Создадете објекти од класа на парови и иницијализирајте ги со минимална вредност на цел број.
  5. Додека ја минуваше картата.
    1. Проверете дали фреквенцијата на тековниот клуч е поголема од доделените објекти.
    2. Ако е точно, тогаш префрлете ги сите клучеви и вредности на други објекти на Pair.
  6. Печатете ги првите три елементи.

Објаснување

Дадена низа е низа со неколку интегритети зачувани во неа. Проблемот вели дека дознајте ги топ 3 повторуваните елементи. Значи, нашата главна идеја е да ги броиме и складираме фреквенциите на секој елемент. Itе го направиме тоа со помош на мапа. Потоа следува друга идеја што е да се прогласи класа и да се користат објектите на таа класа за да се проверат и складираат нашите вредности што можат да бидат наш излез.

Toе ја изброиме секоја фреквенција на елементот, а потоа ќе ја споредиме секоја друга фреквенција на картата, што е поголем број како што го користевме за да откриеме поголемо не во уште три броја.

Да разгледаме пример и да го разбереме ова.

arr [] = {9, 4, 2, 9, 1, 9, 15, 1, 15, 15, 1, 2, 9}

Почнувајќи со броење на фреквенциите на секој елемент присутен во низата. Endе изградиме мапа во која се зачувани сите елементи и нивните фреквенции. Нашата мапа ќе се состои од следниве вредности:

Freq= {1:3, 2:2, 4:1, 9:4,15:3,9:4}

Имаме сè што ни треба, во сето ова треба само да ги откриеме топ 3 повторените броеви. За тоа, ја иницијализираме вредноста на објектите од класа на парови со минималната вредност на целиот број. Traе го поминеме секој од копчињата и нивната фреквенција. Потоа споредете со предметите како x.first, y.first, z.first. И на крајот, ги отпечатиме горните 3 повторени елементи во низа.

Код

C ++ код за да ги пронајдете првите три во низа

#include <bits/stdc++.h>
using namespace std;
void getRepeatedNumbers(int arr[], int n)
{
    if (n < 3)
    {
        cout << "INVALID !! PLEASE ENTER CORRECT INPUT";
        return;
    }
    unordered_map<int, int> fre;
    for (int i = 0; i < n; i++)
        fre[arr[i]]++;

    pair<int, int> x, y, z;
    x.first = y.first = z.first = INT_MIN;

    for (auto val : fre)
    {
        if (val.second > x.first)
        {
            z = y;
            y = x;

            x.first = val.second;
            x.second = val.first;
        }
        else if (val.second > y.first)
        {
            z = y;

            y.first = val.second;
            y.second = val.first;
        }
        else if (val.second > z.first)
        {
            z.first = val.second;
            z.second = val.first;
        }
    }
    cout << "Top three repeated elements are  "<< x.second << " " << y.second<< " " << z.second;
}
int main()
{
    int arr[] = { 9, 4, 2, 9, 1, 9, 15, 1, 15, 15, 1, 2, 9 };
    int n = sizeof(arr) / sizeof(arr[0]);
    getRepeatedNumbers(arr, n);
    return 0;
}
Top three repeated elements are  9 15 1

Java код за наоѓање на тројцата повторени во низата

import java.io.*;
import java.util.*;

class Pair
{
    int first, second;
}
class topThreeRepeatedNumber
{
    public static void getRepeatedNumbers(int[] arr, int n)
    {
        if (n < 3)
        {
            System.out.print("INVALID !! PLEASE ENTER CORRECT INPUT");
            return;
        }
        TreeMap<Integer, Integer> freq = new TreeMap<>();

        for (int i = 0; i < n; i++)
        {
            if (freq.containsKey(arr[i]))
                freq.put(arr[i], 1 + freq.get(arr[i]));
            else
                freq.put(arr[i], 1);
        }

        Pair x = new Pair();
        Pair y = new Pair();
        Pair z = new Pair();
        x.first = y.first = z.first = Integer.MIN_VALUE;

        for (Map.Entry val : freq.entrySet())
        {
            if (Integer.parseInt(String.valueOf(val.getValue())) > x.first)
            {

                z.first = y.first;
                z.second = y.second;
                y.first = x.first;
                y.second = x.second;

                x.first = Integer.parseInt(String.valueOf(val.getValue()));
                x.second = Integer.parseInt(String.valueOf(val.getKey()));
            }
            else if (Integer.parseInt(String.valueOf(val.getValue())) > y.first)
            {
                z.first = y.first;
                z.second = y.second;

                y.first = Integer.parseInt(String.valueOf(val.getValue()));
                y.second = Integer.parseInt(String.valueOf(val.getKey()));
            }
            else if (Integer.parseInt(String.valueOf(val.getValue())) > z.first)
            {
                z.first = Integer.parseInt(String.valueOf(val.getValue()));
                z.second = Integer.parseInt(String.valueOf(val.getKey()));
            }
        }

        System.out.println("Top three repeated elements are " + x.second + ", "+ y.second + ", " + z.second);
    }
    public static void main(String args[])
    {
        int[] arr = { 9, 4, 2, 9, 1, 9, 15, 1, 15, 15, 1, 2, 9 };
        int n = arr.length;
        getRepeatedNumbers(arr, n);
    }
}
Top three repeated elements are 9, 1, 15

Анализа на сложеност

Временска комплексност

Тој) каде „Н“ е бројот на елементи во низата. Поради користењето на Хашмап, успеавме да ја намалиме сложеноста на времето со значителен фактор што го прави линеарен проблемот „Најди ги трите најдобри повторени во низата“.

Комплексноста на просторот

Тој) каде „Н“ е бројот на елементи во низата. Во најлош случај, ќе зачуваме n парови со клучни вредности. Така, вселенската комплексност е исто така линеарна.