使用哈希图的数组中的最大频率数

问题描述 投票：0回答：7

问题：

您将获得一个整数数组，其中包含随机顺序的数字。编写一个程序来查找并返回给定输入中出现次数最多的数字。

如果两个或多个元素竞争最大频率，则返回数组中最先出现的元素。

输入格式：

第 1 行：整数 N，即数组的大小
第 2 行：N 个整数，它们是数组的元素，用空格分隔

输出格式：

最常见的元素

限制：

0<= N <= 10^8

示例输入 1：

13
2 12 2 11 12 2 1 2 2 11 12 2 6

样本输出1：

2

输出不正确，请告知问题所在。 这是代码：

#include <unordered_map>
using namespace std;


int highestFrequency(int *input, int n){
    unordered_map<int, int> map;
    int maxFreq = 0;
    for(int i = 0; i < n; i++){
        if(map.count(input[i]) > 0){
            map[input[i]]++;
            if(map[input[i]] > maxFreq){
                maxFreq = map[input[i]];
            }
        }
        map[input[i]] = 1;
    }
    for(int i = 0; i < n; i++){
        if(map[input[i]] == maxFreq){
            cout << input[i];
        }
    }

    /* Don't write main().
     * the input array is already passed as function argument.
     * Taking input and printing output is handled automatically.
     */ 
}
c++ arrays data-structures hashmap
7个回答
1
投票

我认为这是计算元素频率的有效方法。 unordered_map mp； 

// Traverse through array elements and 
// count frequencies 
for (int i = 0; i < n; i++) 
    mp[arr[i]]++; 

// Traverse through map and print frequencies 
for (auto x : mp) 
    cout << x.first << " " << x.second << endl; 
// found the most frequent item.
 int max_count = 0, res = -1; 
for (auto i : mp) { 
    if (max_count < i.second) { 
        res = i.first; 
        max_count = i.second; 
    } 
}

res就是答案

1
投票

//java解决方案

public static int maxFrequencyNumber(int[] arr){ 
    if(arr.length == 0)
        return -1;
    int maxFreq = 0;
    int number = -1;
    HashMap<Integer,Integer> map = new HashMap<>();
    
    for(int i=0;i<arr.length;i++)
    {
        if(map.containsKey(arr[i]))
        {
            map.put(arr[i],map.get(arr[i])+1);
        }
        else {
            map.put(arr[i], 1);
        }
    }
    // using set data structure
    Set<Integer> keySet = map.keySet();
    for(Integer i:keySet)
    {
        if(map.get(i) > maxFreq)
        {
            number = i;
            maxFreq = map.get(i);
        }
    }
    return number;
}

}

0
投票

我认为这是哈希图中的编码忍者问题之一。 这是我的代码，它是正确的，您可以进行试运行，您会很容易理解

int main(){
    int n;
    cin>>n;
    int arr[n];
    int maxcount=0;
    int maxf=INT32_MIN;
    unordered_map<int,int> freq;

    for(int i=0;i<n;i++){
            cin>>arr[i];
            freq[arr[i]]++;
            if(freq[arr[i]] > maxcount){
                maxcount=freq[arr[i]];
                maxf = arr[i];
            }
        } 
    cout<<maxf<<endl;
    
}
  1. 您可以使用 freq[arr[i]]++ 它会自动更新密钥，当找到新密钥时，它将创建并为其添加值。
  2. 创建一个计数变量，并在发现更多发生时更新它 并将该键值存储在 maxf 中，然后返回它；
0
投票

我不熟悉 C++，但我认为您的代码不起作用的原因是 - 您在迭代 Map 时检查出现的最大值。现在，如果有 2 个具有相同频率的值，则当您使用相等运算符时，最后出现的值将被存储为最终答案，而无需引用具有最大频率的值。这意味着您始终可以将映射值与相同的最大频率值进行比较。 （如map[1] == 2 或map[2] == 2 || map[3]==2）

根据我的说法，您应该保留对元素以及最后一个最大频率的引用。然后最后，迭代数组以检查最大出现值并返回它而不是打印。

这是我的JAVA代码供您参考-``

public static int maxFrequencyNumber(int[] arr){
    HashMap<Integer,Integer> hm=new HashMap<>();

    for (int j : arr) {
        int val = hm.getOrDefault(j, 0) + 1;
        hm.put(j, val);
    }
    int value=-1;
    int currE=arr[0];
    for(int i:arr){
        if(hm.get(i)>value){
            value=hm.get(i);
            currE=i;
        }
    }
    return currE;
}

`

希望这对某人有帮助。另外，如果我的方法错误，请告诉我。

谢谢！

0
投票

public static int maxFrequencyNumber(int[] arr){

    HashMap<Integer, Integer> seen=new HashMap<>();
    for(int i=0;i<arr.length;i++){
         
        int key=arr[i];
        // int count=0;
        if(seen.containsKey(key)) {
             int count=seen.get(key);
             count++;
             seen.put(arr[i], seen.get(key)+1);
        }
        else {
            seen.put(key,1);
        }
    }
        int max_count = 0, res = -1;
         
        for(Entry<Integer, Integer> val : seen.entrySet())
        {
            if (max_count < val.getValue())
            {
                res = val.getKey();
                max_count = val.getValue();
            }
        }
        return res;
 
}
0
投票

您的代码的以下部分有问题：

for(int i = 0; i < n; i++) {
    if(map.count(input[i]) > 0) {
        map[input[i]]++;
        if(map[input[i]] > maxFreq) {
            maxFreq = map[input[i]];
        }
    }
    map[input[i]] = 1;
}

更具体地说，

map[input[i]] = 1
不断重置
map[input[i]]++;
中递增的值。这会导致您的 maxFreq 为 atmost = 2（因为 
maxFreq = map[input[i]];
）。要解决此问题，只需将您的 
map[input[i]] = 1;
放入 
else
语句中即可。

更准确地说，代码中有问题的部分包括不必要的

if(map.count(input[i]) > 0)
，可以简化为：

for(int i = 0; i < n; i++) {
    map[input[i]]++;
    if(map[input[i]] > maxFreq)
        maxFreq = map[input[i]];
}

但是经过所有这些改进，您的代码仍然无法满足指定的条件：

如果两个或多个元素竞争最大频率，则返回数组中最先出现的元素。

为了也满足这个条件，你只需要反向迭代你的数组。下面是我完整的改进代码，使用向量而不是数组：

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

int mF(vector<int> arr) {
  unordered_map <int,int> count;
  int max_freq=0, num, result;

  int i = arr.size();  //Reverse iterating
  while(i--) {         //the vector
    num = arr[i];
    count[num]++;
    if(count[num] >= max_freq) {
      max_freq = count[num];
      result = num;  //Storing the number with maximum frequency
    }
  }
  
  return result;
}

int main() {
  vector<int> arr = {1,9,2,8,3,2,2,1,0,3,9,9,4,8};  //Example list of numbers
  
  cout<<"Maximum Frequency Number = "<<mF(arr);

  return 0;
}

上面代码的主要变化是列表是反向迭代的，并且为了更新最大频率，我们使用 

if(count[num]
>=
 
max_freq)
。

  1. 反向迭代可以让我们得到列表中出现次数最多的数字，最后出现的数字。
    2. if 语句中的
  2. >=
    允许列表中较早出现的具有相同频率的数字将其值存储在 max_freq 中。
-2
投票

导入java.util.HashMap；

公共类MaimumFrequencyNumber {

public static int maxFrequencyNumber(int[] arr){ 
    HashMap<Integer, Integer> hm = new HashMap<>();
    for (int i : arr) {
        hm.put(i, hm.getOrDefault(i, 0) + 1);
    }
    int max = 0, ans = Integer.MIN_VALUE;
    for (int i : arr) {
        if (hm.get(i) > max) {
            max = hm.get(i);
            ans = i;
        }

    }
    return ans;
}
public static void main (String[] args) {
     
    int arr[] = {1, 5, 2, 1, 3, 2, 1}; 
     
    System.out.println(maxFrequencyNumber(arr));
}

}

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.