Знайдзіце тры масівы, якія паўтараюцца ў масіве


Узровень складанасці Лёгка
Часта пытаюцца ў MAQ o9 рашэнні Wipro
масіў гашыш

Праблема «Знайсці тры максімальныя паўторы ў масіве» абвяшчае, што вам дадзена масіў з 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. Калі гэта так, перанясіце ўсе ключы і значэнні на іншыя аб'екты пары.
  6. Раздрукуйце тры верхнія элементы.

Тлумачэнне

Мы атрымліваем масіў з некалькімі цэлымі лікамі, якія ў ім захоўваюцца. Праблема кажа, што высветліце 3 асноўныя элементы, якія паўтараюцца. Такім чынам, наша галоўная ідэя - падлічваць і захоўваць частаты кожнага элемента. Мы будзем рабіць гэта з дапамогай карты. Потым узнікае іншая ідэя, якая заключаецца ў аб'яўленні класа і выкарыстанні аб'ектаў гэтага класа для праверкі і захоўвання нашых значэнняў, якія могуць быць высновай.

Мы збіраемся падлічваць частату кожнага элемента, а потым параўноўваць з любой іншай частатой на карце, што з'яўляецца большым лікам, як мы выкарыстоўвалі, каб даведацца большае не ў трох іншых ліках.

Давайце разгледзім прыклад і зразумеем гэта.

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

Пачынаючы з падліку частот кожнага элемента, які прысутнічае ў масіве. У выніку мы пабудуем карту, на якой будуць захоўвацца ўсе элементы і іх частаты. Наша карта будзе складацца з наступных значэнняў:

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

У нас ёсць усё, што нам трэба, ва ўсім гэтым нам проста трэба даведацца 3 верхніх паўторных нумары. Для гэтага мы ініцыялізуем значэнне аб'ектаў парнага класа з мінімальным значэннем цэлага ліку. Мы пройдзем кожны з клавіш і іх частату. Затым параўнайце з аб'ектамі як x.first, y.first, z.first. І ў рэшце рэшт, мы друкуем тры масівы, якія паўтараюцца, у масіве.

код

Код 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

Аналіз складанасці

Складанасць часу

Аб (п) дзе "П" - колькасць элементаў у масіве. З-за выкарыстання Hashmap мы змаглі паменшыць складанасць часу на істотны фактар, робячы праблему «Знайсці тры лепшыя паўтараныя ў масіве» лінейнай.

Касмічная складанасць

Аб (п) дзе "П" - колькасць элементаў у масіве. У горшым выпадку мы будзем захоўваць n пар ключ-значэнне. Такім чынам, касмічная складанасць таксама лінейная.