最小元素正好重复K次  


难度级别 中等
经常问 贝尔扎巴尔 科姆利媒体 Netskope Nvidia公司 操作 ServiceNow UHG Optum
排列 哈希

给我们一个大小为n的数组A []。 我们必须找到在元素中精确重复k次的最小元素 排列.

使用案列  

输入

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

K = 3

输出

频率为K的最小元素是:2

方法1:蛮力  

大意

对于数组中的每个元素,我们都可以遍历整个数组来找到其频率,如果它的频率等于K,那么我们将采用我们之前的答案和该元素中的最小值。 最后,我们将打印最终答案。

查找精确重复K次的最小元素的算法

  1. 用false初始化变量'flag'。 标记表示我们是否找到了频率为K的元素。
  2. 对0到n-1的I进行循环
    1. 用零初始化变量计数,该变量计数将对数组中A [i]的频率进行计数。
    2. 对j进行循环,范围为0到n-1
      1. 如果A [j]等于A [i],则将计数递增1。
    3. 如果count等于K,则更新ans = min(ans,A [i])。
  3. 检查,如果标志为true,则打印ans,否则打印不存在频率为K的元素。
参见
查找可以由字符Leetcode解决方案形成的单词

实施

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的嵌套循环。因此,总的时间复杂度为 O(N ^ 2).

空间复杂度

我们正在使用恒定的空间。 所以空间复杂度是 O(1).

方法2:使用哈希  

大意

我们可以将每个元素的频率存储在哈希表中。

参见
计算给定总和的对

之后,我们可以遍历哈希表以找到频率恰好为K的最小元素。

查找精确重复K次的最小元素的算法

  1. 如果每个元素在哈希表中,则存储频率。
  2. 用false初始化变量'flag'。 标记表示我们是否找到了频率为K的元素。
  3. 迭代哈希表并找到频率为K的最小元素。
  4. 如果该标志为true,则打印ans,否则打印不存在频率为K的元素。

举例说明

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

K = 3

对于此数组,哈希表将如下所示:

最小元素正好重复K次Pin

实施

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次的最小元素的复杂度分析

时间复杂度

我们只遍历数组一次,所以时间复杂度是 上).

参见
将数组更改为数字从1到N的排列

空间复杂度

我们正在维护一个哈希表来存储数组中元素的频率,因此空间复杂度为 上).

參考資料