Массив дээр давтагдсан шилдэг гурвыг ол


Хэцүү байдлын түвшин Easy
Байнга асуудаг MAQ o9 шийдэл Випро фирмийн
Array Хаш

"Массивт давтагдсан гурвыг олох" гэсэн асуудалд танд an гэсэн хариулт өгсөн болно массив дотор нь хэдэн давтагдсан тоо бүхий 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. Тунхагла газрын зураг болон хэрэглэгчийн тодорхойлсон Pair нэртэй анги.
  2. Хэрэв дор хаяж гурван утга байхгүй бол буцах.
  3. Оролтын элемент бүрийн давтамжийг тоолж хадгална массив газрын зураг дээр байрлуул.
  4. Хос ангийн объектуудыг үүсгээд бүхэл тооны хамгийн бага утгаар эхлүүлнэ.
  5. Газрын зургаар явж байхдаа.
    1. Одоогийн түлхүүрийн давтамж нь оноосон объектуудаас их байгаа эсэхийг шалгана уу.
    2. Хэрэв үнэн бол бүх түлхүүрүүд болон утгуудыг Pair-ийн бусад объектууд руу шилжүүлээрэй.
  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 гэж объектуудтай харьцуул. Эцэст нь бид массивын дотор давтагдсан шилдэг 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

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

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

O (N) хаана "N" нь массив дахь элементүүдийн тоо юм. Hashmap-ийг ашигласнаар бид цаг хугацааны нарийн төвөгтэй байдлыг “Массивт давтаж давсан гурвыг олох” асуудлыг шийдвэрлэх хүчин зүйлээр багасгаж чадсан.

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

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