[215] Kth Largest Element in an Array

寫到這一題之後不知道為什麼認真的累了XD
然後就頹廢了兩天QQ
這禮拜應該要開始大量的看題目和解答,
沒時間慢慢想慢慢寫了...(傷心)

給一個unsorted array,
回傳它的第k大的值.
第一個當然是先用qsort解決它XD
不過聽說有更快的方法Orz
還看到了沒看過的algo !!
Blum-Floyd-Pratt-Rivest-Tarjan algorithm
以上 Orz

Kth Largest Element in an Array
int *compare(const void *a , const void *b){
    return (*(int*)b - *(int*)a);
}

int findKthLargest(int* nums, int numsSize, int k) {
    qsort(nums,numsSize,sizeof(int),compare);
    return nums[k-1];
}

「20250927更新」

嗯........用linked list 硬幹了一場應該是對的

但是很可惜超時了XDDDDDD

把它留在這裡以滋紀念, 我還是覺得我有進步啊~(大笑)

據說要用quick selection 是嗎晚點再寫寫看

struct ListNode* head;

struct ListNode* create(int val)

{

struct ListNode* ret = calloc (1, sizeof(struct ListNode));

ret->val = val;

ret->next = NULL;

return ret;

}

void insertHeap(int val)

{

struct ListNode* ret;

ret = create(val);

if (head->val <= val) // new head

{

ret->next = head;

head = ret;

}

else

{

struct ListNode* ptr;

ptr = head;

while (ptr->next != NULL && (ptr->next->val > val))

ptr = ptr->next;

if (ptr->next != NULL)

{

ret->next = ptr->next;

ptr->next = ret;

}

else // add to tail

ptr->next = ret;

}

return;

}

int findKthLargest(int* nums, int numsSize, int k) {

head = create(nums[0]);

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

insertHeap(nums[i]);

struct ListNode* ptr = head;

for (int i=1; i<k; i++)

{

//printf("%d\n", ptr->val);

ptr = ptr->next;

}

return ptr->val;

}

但我現在有點懶得寫啊哈哈哈（乾笑）

想說要寫一個quick sort 但好像寫出了奇怪的東西?!

感覺也沒錯啊QQ 但是超時了Orz 是在瞎忙什麼哈哈哈 （崩潰）

void swap(int *a, int *b)

{

int tmp = *a;

*a = *b;

*b = tmp;

return;

}

void myqsort(int *nums, int left, int right)

{

if (left>=right)

return;

if (right -left <2)

{

if (nums[left]> nums[right])

swap(&nums[left], &nums[right]);

return;

}

int pivot = nums[left];

int l = left+1;

int r = right;

while (l<r)

{

while (r>left && nums[r]>=pivot)

r--;

while (l<right && nums[l]< pivot)

l++;

if (l<r)

swap(&nums[l], &nums[r]);

else

{

swap(&nums[left], &nums[r]);

myqsort(nums,left,r-1);

myqsort(nums,r+1,right);

}

}

//myqsort(nums,left,r-1);

//myqsort(nums,r+1,right);

}

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

{

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

}

int findKthLargest(int* nums, int numsSize, int k) {

myqsort(nums,0, numsSize-1);

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

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

printf("%d %d\n", i , nums[i]);

return nums[numsSize-k];

}

沒想到自己以前存的qqsort竟然可以PASS = =+

難道要拿出婷婷教授的筆記回來看了嗎 囧

看來要過兩天再回來寫一次了Orz

void swap(int *a, int *b)

{

int tmp = *a;

*a = *b;

*b = tmp;

return;

}

void myqsort(int *nums, int left, int right)

{

int l=left, r=right;

int mid = (l+r)/2;

int pivot= nums[mid];

while (l<=r)

{

while (nums[l]< pivot)

l++;

while (nums[r]>pivot)

r--;

if (l<=r)

{

swap(&nums[l],&nums[r]);

l++;

r--;

}

}

if (left<r)

myqsort(nums,left,r);

if (l<right)

myqsort(nums,l,right);

}

int findKthLargest(int* nums, int numsSize, int k) {

myqsort(nums,0, numsSize-1);

return nums[numsSize-k];

}