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上以上问题的一个哈希表解法,不知道怎么构造哈希表,还请各位大神指教
在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;
}
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。