ອົງປະກອບນ້ອຍທີ່ສຸດຊ້ ຳ ຊ້ ຳ ແນ່ນອນ K Times  


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ ເບລາຊາບາ ສື່ມວນຊົນ Komli Netskope Nvidia Opera ServiceNow UHG Optum
Array Hash string

ພວກເຮົາແມ່ນໄດ້ຮັບການຈັດລຽງ A [] ຕາມຂະ ໜາດ n. ພວກເຮົາຕ້ອງຊອກຫາອົງປະກອບນ້ອຍທີ່ສຸດທີ່ຖືກຊ້ ຳ ຄືນຢ່າງແນ່ນອນ k ເທື່ອໃນ array.

ຍົກຕົວຢ່າງ  

ການປ້ອນຂໍ້ມູນ

A [] = {1, 2, 2, 5, 5, 2, 5}

K = 3

ຜົນຜະລິດ

ອົງປະກອບນ້ອຍທີ່ສຸດທີ່ມີຄວາມຖີ່ K ແມ່ນ: 2

ວິທີການທີ 1: ກຳ ລັງແຮງ  

ຄວາມ​ຄິດ​ຫຼັກ

ສຳ ລັບທຸກໆອົງປະກອບທີ່ຢູ່ໃນແຖວ, ພວກເຮົາສາມາດຊອກຫາຄວາມຖີ່ຂອງມັນໄດ້ໂດຍການຂ້າມອາເລມທັງ ໝົດ ແລະຖ້າຄວາມຖີ່ຂອງມັນເທົ່າກັບ K, ແລ້ວພວກເຮົາຈະ ນຳ ເອົາ ຄຳ ຕອບທີ່ ໜ້ອຍ ທີ່ສຸດຂອງພວກເຮົາມາກ່ອນແລະອົງປະກອບນີ້. ໃນທີ່ສຸດ, ພວກເຮົາຈະພິມ ຄຳ ຕອບສຸດທ້າຍຂອງພວກເຮົາ.

ສູດການຄິດໄລ່ ສຳ ລັບການຊອກຫາອົງປະກອບນ້ອຍທີ່ສຸດຊ້ ຳ ຊ້ ຳ ແນ່ນອນ K Times

  1. ເລີ່ມຕົ້ນ 'ຕົວທຸງ' ຕົວແປທີ່ບໍ່ຖືກຕ້ອງ. ໝາຍ ເຖິງຖ້າພວກເຮົາພົບເຫັນອົງປະກອບໃດ ໜຶ່ງ ທີ່ມີຄວາມຖີ່ K ຫລືບໍ່.
  2. ດໍາເນີນການ loop ສໍາລັບ I ໃນລະດັບ 0 ເຖິງ n-1
    1. ເລີ່ມຕົ້ນຕົວແປທີ່ມີຕົວແປກັບສູນເຊິ່ງຈະນັບຄວາມຖີ່ຂອງ A [i] ໃນຂບວນ.
    2. ດໍາເນີນການ loop ສໍາລັບ j ໃນລະດັບ 0 ເຖິງ n-1
      1. ຖ້າ A [j] ເທົ່າກັບ A [i], ຕົວເລກເພິ່ມຂື້ນ 1.
    3. ຖ້ານັບແມ່ນເທົ່າກັບ K, ໃຫ້ປັບປຸງ ans = min (ans, A [i]).
  3. ກວດເບິ່ງ, ຖ້າທຸງແມ່ນຄວາມຈິງແລ້ວພິມ ຄຳ ຕອບ, ຖ້າບໍ່ດັ່ງນັ້ນພິມວ່າບໍ່ມີອົງປະກອບໃດທີ່ມີຄວາມຖີ່ K.
ເບິ່ງ
ຊອກຫາ ຄຳ ສັບທີ່ສາມາດສ້າງຂື້ນໂດຍຕົວອັກສອນ Leetcode Solution

ການປະຕິບັດ

ໂປຣແກຣມ C ++

#include <bits/stdc++.h>
using namespace std;
void smallestElementRepeatedExactlyKTimes(vector<int> A, int K)
{
    int n = A.size();
    bool flag = false;
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        int count = 0;
        for (int j = 0; j < n; j++)
        {
            if (A[i] == A[j])
            {
                count++;
            }
        }
        if (count == K)
        {
            if (flag == false)
            {
                flag = true;
                ans = A[i];
            }
            else
            {
                ans = min(ans, A[i]);
            }
        }
    }
    if (flag == false)
    {
        cout << "There is no element with frequency K.";
    }
    else
    {
        cout << "Smallest element with frequency K is: " << ans;
    }
    return;
}
int main()
{
    vector<int> A = {1, 2, 2, 5, 5, 2, 5};
    int K = 3;
    smallestElementRepeatedExactlyKTimes(A, K);
    return 0;
}
Smallest element with frequency K is: 2

ໂຄງການ JAVA

public class Main
{
    static void smallestElementRepeatedExactlyKTimes(int A[],int K)
    {
        int n = A.length;
        boolean flag = false;
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            int count = 0;
            for (int j = 0; j < n; j++)
            {
                if (A[i] == A[j])
                {
                    count++;
                }
            }
            if (count == K)
            {
                if (flag == false)
                {
                    flag = true;
                    ans = A[i];
                }
                else
                {
                    ans = Math.min(ans, A[i]);
                }
            }
        }
        if (flag == false)
        {
            System.out.print("There is no element with frequency K.");
        }
        else
        {
            System.out.print("Smallest element with frequency K is: "+ ans);
        }
        return;
    }
  public static void main(String[] args) {
    int A[] = {1, 2, 2, 5, 5, 2, 5};
        int K = 3;
        smallestElementRepeatedExactlyKTimes(A, K);
  }
}
Smallest element with frequency K is: 2

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບການຊອກຫາອົງປະກອບນ້ອຍທີ່ສຸດຊ້ ຳ ຊ້ ຳ ແນ່ນອນ K Times

ຄວາມສັບສົນເວລາ

ພວກເຮົາ ກຳ ລັງໃຊ້ສອງວົງແຫວນທີ່ມີຮັງ, ທັງຂະ ໜາດ N. ດັ່ງນັ້ນຄວາມສັບສົນເວລາທັງ ໝົດ ແມ່ນ O (N ^ 2).

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

ພວກເຮົາ ກຳ ລັງໃຊ້ພື້ນທີ່ຄົງທີ່. ສະນັ້ນຄວາມສັບສົນໃນພື້ນທີ່ແມ່ນ O (1).

ວິທີທີ່ 2: ການ ນຳ ໃຊ້ hashing  

ຄວາມ​ຄິດ​ຫຼັກ

ພວກເຮົາສາມາດເກັບຮັກສາຄວາມຖີ່ຂອງແຕ່ລະອົງປະກອບໃນຕາຕະລາງ hash.

ເບິ່ງ
ນັບຄູ່ພ້ອມດ້ວຍຍອດລວມ

ຫລັງຈາກນັ້ນ, ພວກເຮົາພຽງແຕ່ສາມາດຂ້າມຕາຕະລາງ hash ເພື່ອຊອກຫາອົງປະກອບນ້ອຍທີ່ສຸດທີ່ມີຄວາມຖີ່ຂອງ K ຢ່າງແນ່ນອນ.

ສູດການຄິດໄລ່ ສຳ ລັບການຊອກຫາອົງປະກອບນ້ອຍທີ່ສຸດຊ້ ຳ ຊ້ ຳ ແນ່ນອນ K Times

  1. ເກັບຮັກສາຄວາມຖີ່ຂອງການຖ້າຫາກວ່າແຕ່ລະອົງປະກອບໃນຕາຕະລາງ hash.
  2. ເລີ່ມຕົ້ນ 'ຕົວທຸງ' ຕົວແປທີ່ບໍ່ຖືກຕ້ອງ. ໝາຍ ເຖິງຖ້າພວກເຮົາພົບເຫັນອົງປະກອບໃດ ໜຶ່ງ ທີ່ມີຄວາມຖີ່ K ຫລືບໍ່.
  3. Iterate ຕາຕະລາງ hash ແລະຊອກຫາອົງປະກອບນ້ອຍທີ່ສຸດດ້ວຍຄວາມຖີ່ K.
  4. ຖ້າ ໝາຍ ທຸງເປັນຄວາມຈິງແລ້ວໃຫ້ພິມ ຄຳ ຕອບ, ຖ້າບໍ່ດັ່ງນັ້ນພິມວ່າບໍ່ມີອົງປະກອບໃດທີ່ມີຄວາມຖີ່ K.

ເຂົ້າໃຈກັບຕົວຢ່າງ

A [] = {1, 2, 2, 5, 5, 2, 5}

K = 3

ສຳ ລັບອາເລນີ້, ຕາຕະລາງ hash ຈະມີລັກສະນະດັ່ງນີ້:

ອົງປະກອບນ້ອຍທີ່ສຸດຊ້ ຳ ຊ້ ຳ ແນ່ນອນ K TimesPin

ການປະຕິບັດ

ໂປຣແກຣມ C ++

#include <bits/stdc++.h>
using namespace std;
void smallestElementRepeatedExactlyKTimes(vector<int> A, int K)
{
    int n = A.size();
    bool flag = false;
    int ans = 0;
    unordered_map<int, int> hash_table;
    for (int i = 0; i < n; i++)
    {
        hash_table[A[i]]++;
    }
    for (auto element : hash_table)
    {
        if (element.second == K)
        {
            if (flag == false)
            {
                flag = true;
                ans = element.first;
            }
            else
            {
                ans = min(ans, element.first);
            }
        }
    }
    if (flag == false)
    {
        cout << "There is no element with frequency K.";
    }
    else
    {
        cout << "Smallest element with frequency K is: " << ans;
    }
    return;
}
int main()
{
    vector<int> A = {1, 2, 2, 5, 5, 2, 5};
    int K = 3;
    smallestElementRepeatedExactlyKTimes(A, K);
    return 0;
}
Smallest element with frequency K is: 2

ໂຄງການ JAVA

import java.util.*; 
public class Main
{
    static void smallestElementRepeatedExactlyKTimes(int A[],int K)
    {
        int n = A.length;
        boolean flag = false;
        int ans = 0;
        HashMap<Integer, Integer> hash_table = new HashMap<Integer, Integer>(); 
        for (int i = 0; i < n; i ++) 
        {
            if (hash_table.containsKey(A[i])) 
            {
                hash_table.put(A[i], hash_table.get(A[i]) + 1); 
            }
            else{
                hash_table.put(A[i], 1);
            }
        }
        for(Map.Entry element: hash_table.entrySet())
        {
            if(((int)element.getValue()==K))
            {
                if(flag==false)
                {
                    flag=true;
                    ans=((int)(element.getKey()));
                }
                else{
                    ans=Math.min(ans,((int)(element.getKey())));
                }
            }
        }
        if (flag == false)
        {
            System.out.print("There is no element with frequency K.");
        }
        else
        {
            System.out.print("Smallest element with frequency K is: "+ ans);
        }
        return;
    }
  public static void main(String[] args) {
    int A[] = {1, 2, 2, 5, 5, 2, 5};
        int K = 3;
        smallestElementRepeatedExactlyKTimes(A, K);
  }
}
Smallest element with frequency K is: 2

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບການຊອກຫາອົງປະກອບນ້ອຍທີ່ສຸດຊ້ ຳ ຊ້ ຳ ແນ່ນອນ K Times

ຄວາມສັບສົນເວລາ

ພວກເຮົາ ກຳ ລັງຂີດເສັ້ນແຖວພຽງແຕ່ຄັ້ງດຽວເທົ່ານັ້ນ, ສະນັ້ນຄວາມສັບສົນເວລາກໍ່ຍັງມີຢູ່ ໂອ (N).

ເບິ່ງ
ປ່ຽນ Array ເປັນການອະນຸຍາດຕົວເລກນັບຕັ້ງແຕ່ 1 ເຖິງ N

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

ພວກເຮົາ ກຳ ລັງຮັກສາຕາຕະລາງ hash ເພື່ອເກັບຄວາມຖີ່ຂອງອົງປະກອບຕ່າງໆໃນອາເລດັ່ງນັ້ນຄວາມສັບສົນໃນອະວະກາດ ໂອ (N).

ເອກະສານ