ຊອກຫາສາມອັນດັບທີ່ຊ້ ຳ ຊ້ອນໃນຂບວນ  


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ MAQ o9 ວິທີແກ້ໄຂ Wipro
Array Hash

ບັນຫາ "ຊອກຫາສາມອັນທີ່ຊ້ ຳ ຊ້ອນກັນໃນອາເລນ" ລະບຸວ່າທ່ານຖືກມອບໃຫ້ array ຂອງ ຈຳ ນວນ n ທີ່ມີບາງຕົວເລກຊ້ ຳ ຊ້ອນໃນມັນ. ວຽກງານຂອງທ່ານແມ່ນເພື່ອຊອກຫາ 3 ຕົວເລກທີ່ຊ້ ຳ ຊ້ອນຢູ່ໃນອັນດັບ ໜຶ່ງ.

ຍົກຕົວຢ່າງ  

ຊອກຫາສາມອັນດັບທີ່ຊ້ ຳ ຊ້ອນໃນຂບວນPin

[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. ນັບແລະເກັບຮັກສາຄວາມຖີ່ຂອງແຕ່ລະສ່ວນປະກອບຂອງວັດສະດຸປ້ອນ array ແລະໃສ່ໃນແຜນທີ່.
  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 ++ ເພື່ອຊອກຫາສາມອັນດັບທີ່ຊ້ ຳ ຊ້ອນກັນໃນ array

#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 ເພື່ອຊອກຫາສາມອັນດັບທີ່ຊ້ ຳ ຊ້ອນໃນ array

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, ພວກເຮົາສາມາດຫຼຸດຜ່ອນຄວາມສັບສົນຂອງເວລາໂດຍປັດໃຈທີ່ ສຳ ຄັນທີ່ເຮັດໃຫ້ບັນຫາ "ຊອກຫາສາມອັນທີ່ຊ້ ຳ ຊ້ອນໃນແຖວ" linear.

ເບິ່ງ
ນັບ Substrings ທີ່ມີ ຈຳ ນວນເທົ່າກັບ 0s, 1s ແລະ 2s

ຄວາມສັບສົນໃນອະວະກາດ

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ໃນກໍລະນີທີ່ຮ້າຍແຮງທີ່ສຸດ, ພວກເຮົາຈະເກັບຮັກສາ n ຄູ່ທີ່ມີຄ່າ ສຳ ຄັນ. ດັ່ງນັ້ນຄວາມສັບສົນໃນພື້ນທີ່ຍັງເປັນເສັ້ນ.