第一个元素在数组中出现k次  


难度级别 易得奖学金
经常问 亚马逊 远足 PayU SAP实验室 Teradata数据 Wipro 朝圣 百会
排列 哈希

我们给了一个数字“ k”和一个整数数组。 问题“数组中第一个元素出现k次”表示要找出数组中第一个元素恰好在数组中出现k次。 如果数组中没有元素出现k次,则返回-1。

使用案列  

查找范围内缺少的元素Pin

Arr[]={1,4,5,2,4,2,7},  k=2
4

说明

在此示例中,有两个元素出现了k次。 4和2正好存在k次,但是4是第一个出现k次。 所以我们返回4。

算法  

  1. 声明一个 哈希图.
  2. 遍历数组。
    • 计算数组中每个元素的频率并将其存储到映射中。
  3. 再次遍历数组,并检查每个数组元素的频率是否等于k。
    • 如果条件满足,则返回该元素。

说明

我们的输入值为 整数 排列 和一个整数k。 问题陈述要求找出正好出现k次的数组中的第一个元素。 为了解决这个问题,我们将使用 哈希。 散列是减少时间复杂度的一种可能方法。 它的成本 O(N) 时间复杂度。

我们将计算并存储地图中每个元素的频率。 假设一个元素在数组中出现3次,我们将其与该元素一起的频率设置为3。 HashMap可以用于存储键和值。 我们将所有元素存储为键,并将其频率存储为HashMap中的值。 然后,我们将运行一个循环并遍历一个数组,然后选择每个元素并检查它们的频率。 如果发现任何元素的频率等于k,那么我们将返回该元素。 由于我们正在遍历数组,因此如果元素与发生一起出现了k次。 那么肯定它将是第k个没有出现的元素。

参见
找到差异Leetcode解决方案

让我们考虑一个例子:

arr [] = {2,4,6,4,2,1,},k = 2

我们将在地图中存储元素之后,将元素作为键存储,并将其频率作为值存储在地图中:

myMap={1:1, 2:2, 4:2, 6:1};

我们将检查每个数组元素,从第0个索引开始,我们将开始遍历数组

i = 0,

如果每个数组的频率[i] == k:

2的频率为2,它等于k,也等于k出现的第一个元素,因此返回arr [i],输出为2。

如果任何一个元素的频率与“ k”不匹配,那么我们将返回-1。

代码  

C ++代码查找数组中出现k次的第一个元素

#include<iostream>
#include <unordered_map>

using namespace std;

int firstElement(int arr[], int n, int k)
{
    unordered_map<int, int> freqMap;

    for (int i=0; i<n; i++)
        freqMap[arr[i]]++;

    for (int i=0; i<n; i++)
        if (freqMap[arr[i]] == k)
            return arr[i];

    return -1;
}
int main()
{
    int arr[] = {2,4,6,4,2,1,6};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << firstElement(arr, n, k);
    return 0;
}
2

Java代码查找数组中出现k次的第一个元素

import java.util.HashMap;

class firstKOccuringElement
{
    public static int getFirstElement(int arr[], int n, int k)
    {
        HashMap<Integer, Integer> freqMap = new HashMap<>();
        for (int i = 0; i < n; i++)
        {
            int a = 0;
            if(freqMap.containsKey(arr[i]))
            {
                freqMap.put(arr[i], freqMap.get(arr[i])+1);
            }
            else
            {
                freqMap.put(arr[i], 1);
            }
        }
        for (int i = 0; i < n; i++)
        {
            if (freqMap.get(arr[i]) == k)
            {
                return arr[i];
            }
        }
        return -1;
    }
    public static void main(String[] args)
    {
        int arr[] = {2,4,6,4,2,1,6};
        int n = arr.length;
        int k = 2;
        System.out.println(getFirstElement(arr, n, k));
    }
}
2

复杂度分析  

时间复杂度

O(N) 哪里 “ n” 是数组中元素的数量。 在这里,由于我们使用了哈希图,因此我们能够在O(1)时间内执行操作。

参见
打印给定整数数组的所有不同元素

空间复杂度

O(N) 哪里 “ n” 是数组中元素的数量。 最坏的情况是所有元素都不同。 我们必须将所有N个元素存储到地图中,这将占用线性空间。