时间戳

首页 > 解决方案 > 查找频率最高的元素（如果可能的话，最小的）及其在整数数组中的出现次数

c++ - 查找频率最高的元素（如果可能的话，最小的）及其在整数数组中的出现次数

问题描述

问题：找到2件事

请尽可能简单地解决问题，不要使用指针或任何高级容器，如 hashtable、pair 或 map（我是初学者）

例如：

{1, 2, 8, 2, 5, 0, 5}

答案是 2 和 2（元素2和5两者都出现两次但2最小）

这是代码，但它只找到最高出现的权利。

int A[] = {1, 2, 8, 2, 5, 0, 5};
int N = 7;
    int maxCount = 0;
    int minMode = 0;
    for (int i = 0; i <= N - 1; i++) {
           int count = 0;
           for (int j = 0; j <= N - 1; j++) {
             if (A[i] == A[j])
                 count++;
       }
      if (count >= maxCount)
        {
            maxCount = count;
            minMode = A[i];
        }

     }
        cout << maxCount << " " << minMode << endl;

标签： c++arraysalgorithmintegerfind-occurrences

解决方案

这个问题是 O(n)，但不使用结构，它变成 O(n²)。

这是一个简单的 O(n²) 解决方案：

int main(){    
    int A[7] = {1, 2, 8, 2, 5, 0, 5};
    int value, occurrences;
    int maxValue = 99999999, maxOccurrences = 0;
    for(int i = 0; i < 7; i++){
        value = A[i]; occurrences = 0;
        for(int j = 0; j < 7; j++) if(A[j] == value) occurrences++;
        if(occurrences > maxOccurrences){
            maxValue = value; maxOccurrences = occurrences;
        }
        else if(occurrences == maxOccurrences){
            if(value < maxValue) {
                maxValue = value; 
                maxOccurrences = occurrences; 
            }
        }       
    }
    cout<<maxValue<<" occurs "<<maxOccurrences<<" times"<<endl;
}

我们将 maxValue 初始化为一个非常大的数字，只是为了帮助这样一个事实，即如果两个数字出现相同的次数，则将选择最小值。

然后我们只是迭代和计数。

一个可能的优化是：假设您在数组中搜索 5。总是找到 5，将出现次数添加到数量并将数组值设置为 -1，所以当你最终从它开始时，你知道它是 -1，你可以跳过那个元素。

推荐阅读