Majority Element[leetcode]

Question

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
求leetcode上以上问题的一个哈希表解法，不知道怎么构造哈希表，还请各位大神指教

Answer 1

已在leetcode上验证过了.

typedef struct Node {
    int val, count;
} Node;

typedef struct HASH {
    Node *np;
    int size, capacity;
} HASH;

#define N 509

#define HASH_VAL(n) abs((n) % N)

static int ensureCapacity(HASH *hp) 
{
    int size, capacity;
    Node *np;

    size = hp->size;
    capacity = hp->capacity;
    if (size < capacity)
        return 0;
    if (capacity == 0)
        capacity = 8;
    else
        capacity <<= 1;
    np = (Node*)realloc(hp->np, capacity * sizeof(Node));
    if (np == NULL)
        return -1;
    hp->capacity = capacity;
    hp->np = np;
    return 0;
}

static void freeHashTab(HASH htab[], int n)
{
    int i;
    for (i = 0; i < n; i++)
        if (htab[i].np)
            free(htab[i].np);    
}

int majorityElement(int arr[], int n) 
{
    HASH htab[N], *hb;
    int i, j, cur, hval, res;

    memset(htab, 0, N * sizeof(HASH));
    for (i = 0; i < n; i++) {
        cur = arr[i];
        hval = HASH_VAL(cur);
        hb = &htab[hval];
        for (j = 0; j < hb->size; j++)
            if (hb->np[j].val == cur)
                break;
        if (j == hb->size) {
            if (ensureCapacity(hb) == -1)
                goto err;
            hb->np[j].val = cur;
            hb->np[j].count = 1;
            hb->size++; 
        } else {
            hb->np[j].count++;
        }
        if (hb->np[j].count > n / 2) {
            res = hb->np[j].val;
            freeHashTab(htab, N);
            return res;
        } 
    }
    
err:
    freeHashTab(htab, N);
    return -1;    
}