佚名通过本文主要向大家介绍了majority element,169 majority element,majority,majority是什么意思,a majority of的用法等相关知识,希望对您有所帮助,也希望大家支持linkedu.com www.linkedu.com
问题：Majority Element[leetcode]
描述:
解决方案1:
描述:
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上以上问题的一个哈希表解法，不知道怎么构造哈希表，还请各位大神指教
解决方案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;
}