[31] Kth Largest Element in a Stream

靠杯喔～這題用C寫絕對不是medium 吧~_~

最好是20分鐘可以寫完啦

（兩天後更）

天要亡我啊～我根本不會寫扣吧

用C寫變型版的heap真是要命啊

typedef struct {

int *heap;

int h_size;

int h_idx;

int k;

} KthLargest;

void swap(int *a, int *b)

{

int tmp = *a;

*a=*b;

*b= tmp;

}

void push(KthLargest* obj, int val) {

if (obj->h_idx+1>obj->k && obj->heap[0]>val)

return;

int move=obj->h_idx;

int parent= (move-1)/2;

obj->heap[obj->h_idx++]=val;

while(parent>=0 && obj->heap[parent]> obj->heap[move])

{

swap(&obj->heap[parent], &obj->heap[move]);

move = parent;

parent= (parent-1)/2;

}

}

void pop(KthLargest* obj) {

swap(&obj->heap[0],&obj->heap[obj->h_idx-1]);

obj->h_idx--;

int l, r, move;

int idx=0;

while (1)

{

l= 2*idx+1;

r= 2*idx+2;

move = idx;

if (l<obj->h_idx && obj->heap[move]>obj->heap[l])

move = l;

if (r<obj->h_idx && obj->heap[move]>obj->heap[r])

move = r;

if (move == idx)

break;

swap(&obj->heap[idx], &obj->heap[move]);

idx= move;

}

}

void createHeap(KthLargest* obj, int* nums, int numsSize) {

for (int i=0; i<numsSize; i++)

{

push(obj, nums[i]);

if (obj->h_idx>obj->k)

pop(obj);

}

return;

}

int kthLargestAdd(KthLargest* obj, int val) ;

KthLargest* kthLargestCreate(int k, int* nums, int numsSize) {

KthLargest* obj = calloc (1, sizeof(KthLargest));

obj->k = k;

obj->h_size = (k>numsSize)? k: numsSize;

obj->heap = calloc (obj->h_size+1 , sizeof(int));

obj->h_idx =0;

#if 1

createHeap(obj, nums, numsSize);

#else

for (int i=0; i<numsSize; i++)

kthLargestAdd(obj, nums[i]);

#endif

return obj;

}

int kthLargestAdd(KthLargest* obj, int val) {

push(obj, val);

if (obj->h_idx>obj->k)

pop(obj);

return obj->heap[0];

}

void kthLargestFree(KthLargest* obj) {

free(obj);

}

應該要用heap 寫一次吧Orz 好懶啊嗚嗚嗚（痛哭）

typedef struct {

int *mq;

int top;

int k;

} KthLargest;

int comp(const void *a, const void *b)

{

return (*(int*)b- *(int *)a);

}

KthLargest* kthLargestCreate(int k, int* nums, int numsSize) {

KthLargest* obj = calloc (1, sizeof(KthLargest));

obj->k = k;

obj->mq = calloc (k, sizeof(int));

if (numsSize>0)

{

qsort(nums,numsSize , sizeof(int), comp );

int copy = (k<numsSize)?(k): numsSize;

memcpy (obj->mq, nums, sizeof(int)* copy);

obj->top =copy-1;

}

else

obj->top = -1;

return obj;

}

int kthLargestAdd(KthLargest* obj, int val) {

if ((obj->top == obj->k-1) && obj->mq[obj->top]>=val)

return obj->mq[obj->top];

int *tmp = calloc (obj->k, sizeof(int));

int idx = 0;

while (obj->top>=0 && obj->mq[obj->top]< val)

tmp[idx++]=obj->mq[obj->top--];

obj->mq[++obj->top]=val;

while (obj->top< obj->k-1)

obj->mq[++obj->top]=tmp[--idx];

free(tmp);

return obj->mq[obj->top];

}

void kthLargestFree(KthLargest* obj) {

free(obj->mq);

free(obj);

}

哦原來用兩次qsort 會爆炸呢～

int kthLargestAdd(KthLargest* obj, int val) {

if ((obj->top == obj->k-1) && obj->mq[obj->top]>=val)

return obj->mq[obj->top];

if (obj->top < obj->k-1)

obj->mq[++obj->top]=val;

else

obj->mq[obj->top]=val;

qsort(obj->mq,obj->k , sizeof(int), comp );

return obj->mq[obj->top];

}