c - 在整数数组中查找最大/最小出现次数

Question

我刚刚完成了一个算法，该算法在输入整数数组中查找具有最大/最小出现次数的值。我的想法是对数组进行排序(现在所有出现的都按顺序排列)并使用 <value:occurrences>对存储每个值对应的出现次数。

应该是O(nlogn)复杂性，但我认为有一些常数乘数。我可以做些什么来提高性能？

#include <stdio.h>
#include <stdlib.h>
#include "e7_8.h"

#define N 20
/*Structure for <value, frequencies_count> pair*/
typedef struct {
    int value;
    int freq;
} VAL_FREQ;


void  get_freq(int *v, int n, int *most_freq, int *less_freq) {

    int v_i, vf_i, current_value, current_freq;

    VAL_FREQ* sp = malloc(n*sizeof(VAL_FREQ));
    if(sp == NULL) exit(EXIT_FAILURE);

    mergesort(v,n);

    vf_i = 0;
    current_value = v[0];
    current_freq = 1;
    for(v_i=1; v_i<n+1; v_i++) {
        if(v[v_i] == current_value) current_freq++;
        else{
            sp[vf_i].value = current_value;
            sp[vf_i++].freq = current_freq;
            current_value = v[v_i];
            current_freq = 1;
        }
    }
    /*Finding max,min frequency*/
    int i, max_freq_val, max_freq, min_freq_val, min_freq;

    max_freq = sp[0].freq;
    max_freq_val = sp[0].value;
    min_freq = sp[0].freq;
    min_freq_val = sp[0].value;
    for(i=1; i<vf_i; i++) {
        if(sp[i].freq > max_freq) {
            max_freq = sp[i].freq;
            max_freq_val = sp[i].value;
        }
        if(sp[i].freq < min_freq) {
            min_freq = sp[i].freq;
            min_freq_val = sp[i].value;
        }
    }

    *most_freq = max_freq_val;
    *less_freq = min_freq_val;

    free(sp);
}

Answer 1

使用哈希表来实现键值映射？那应该给你 O(n) 的预期时间。^*

---

_{* 然而，请注意，在最坏的情况下它是 O(n²)。只有当所有条目散列到同一个桶时才会发生这种情况，并且您实际上最终会为每次迭代搜索链表!对于体面的哈希表实现，这种情况发生的可能性确实非常低。}