අරාවෙහි නැවත නැවතත් ඉහළම තිදෙනා සොයා ගන්න


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ 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. සත්‍ය නම්, සියලු යතුරු සහ අගයන් යුගලයේ වෙනත් වස්තු වෙත මාරු කරන්න.
  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

නැවත නැවත අරාවෙහි ඉහළම තිදෙනා සොයා ගැනීමට ජාවා කේතය

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) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ. හැෂ්මැප් භාවිතා කිරීම නිසා, “රේඛාවෙහි නැවත නැවතත් ඉහළම තිදෙනා සොයා ගන්න” යන ගැටලුව ඇති කරන වැදගත් සාධකයක් මගින් අපට කාල සංකීර්ණතාව අඩු කිරීමට හැකි විය.

අභ්‍යවකාශ සංකීර්ණතාව

සාමාන්ය (n) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ. නරකම අවස්ථාවෙහිදී, අපි යතුරු අගයන් යුගල ගබඩා කරමු. මේ අනුව අවකාශයේ සංකීර්ණතාව ද රේඛීය වේ.