最小の要素が正確にK回繰り返された


難易度 ミディアム
よく聞かれる ベルザバール コムリメディア Netskope Nvidiaの Opera ServiceNow UHGオプタム
配列 ハッシュ 文字列

サイズnの配列A []が与えられます。 で正確にk回繰り返される最小の要素を見つける必要があります 配列.

入力

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

K = 3

出力

周波数Kの最小要素は次のとおりです:2

アプローチ1:ブルートフォース

本旨

配列内のすべての要素について、配列全体をトラバースすることでその頻度を見つけることができます。その頻度がKに等しい場合は、前の回答とこの要素の最小値を取得します。 最後に、最終的な回答を印刷します。

正確にK回繰り返される最小要素を見つけるためのアルゴリズム

  1. 変数 'flag'をfalseで初期化します。 フラグは、頻度Kの要素が見つかったかどうかを示します。
  2. 0からn-1の範囲でIのループを実行します
    1. 配列内のA [i]の頻度をカウントするゼロで変数カウントを初期化します。
    2. 0からn-1の範囲でjのループを実行します
      1. A [j]がA [i]と等しい場合、カウントを1ずつインクリメントします。
    3. countがKに等しい場合は、ans = min(ans、A [i])を更新します。
  3. チェックし、フラグがtrueの場合は、ansを出力します。そうでない場合は、頻度Kの要素がないことを出力します。

製品の導入

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回繰り返される最小の要素を見つけるための複雑さの分析

時間の複雑さ

両方ともサイズNのXNUMXつのネストされたループを使用しています。したがって、合計時間計算量は次のようになります。 O(N ^ 2).

スペースの複雑さ

一定のスペースを使用しています。 つまり、スペースの複雑さは O(1).

アプローチ2:ハッシュを使用する

本旨

各要素の頻度をハッシュテーブルに保存できます。

その後、ハッシュテーブルをトラバースして、頻度が正確にKの最小要素を見つけることができます。

正確にK回繰り返される最小要素を見つけるためのアルゴリズム

  1. 各要素がハッシュテーブルにある場合は、頻度を格納します。
  2. 変数 'flag'をfalseで初期化します。 フラグは、頻度Kの要素が見つかったかどうかを示します。
  3. ハッシュテーブルを繰り返し、頻度Kの最小要素を見つけます。
  4. フラグがtrueの場合は、ansを出力します。そうでない場合は、頻度Kの要素がないことを出力します。

例を挙げて理解する

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

K = 3

この配列の場合、ハッシュテーブルは次のようになります。

最小の要素が正確にK回繰り返された

製品の導入

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回繰り返される最小の要素を見つけるための複雑さの分析

時間の複雑さ

配列をトラバースするのはXNUMX回だけなので、時間の複雑さは オン).

スペースの複雑さ

配列内の要素の頻度を格納するためのハッシュテーブルを維持しているため、スペースの複雑さは オン).

リファレンス