215.c

#include<stdio.h>

intfindKthLargest(int*nums, intnumsSize, intk) {
if (k<1||k>numsSize) return0;

intpivot=nums[0];
inti=0, j=numsSize-1;

while (i<j) {
while (i<j&&nums[j] >= pivot)
j--;

nums[i] =nums[j];

while (i<j&&nums[i] <= pivot)
i++;

nums[j] =nums[i];
 }

nums[i] =pivot;

intrightSize=numsSize-i-1; /* size of right sub array */

if (rightSize+1==k) { /* found, it's pivot */
returnnums[i];
 }

if (rightSize >= k) {
returnfindKthLargest(nums+i+1, rightSize, k); /* find in right half */
 }
else {
returnfindKthLargest(nums, i, k-rightSize-1); /* find in left half */
 }
}

voidswap(int*a, int*b) {
intt=*a;
*a=*b;
*b=t;
}

/* another method, diff from Hoare's quicksort */
intfindKthLargest0(int*nums, intnumsSize, intk) {
if (k<1||k>numsSize) return0;

intpivotIndex=0; /* select a pivot, simply use leftest elem */
intpivotValue=nums[pivotIndex];
inti=0; /* store index */
intj; /* sweep index */

swap(&nums[pivotIndex], &nums[numsSize-1]);

for (j=0; j<numsSize-1; j++) {
if (nums[j] <= pivotValue) {
swap(&nums[j], &nums[i]);
i++;
 }
 }

swap(&nums[i], &nums[numsSize-1]);

intrightSize=numsSize-i-1; /* size of right sub array */

if (rightSize+1==k) { /* found, it's pivot */
returnnums[i];
 }

if (rightSize >= k) {
returnfindKthLargest0(nums+i+1, rightSize, k); /* find in right half */
 }
else {
returnfindKthLargest0(nums, i, k-rightSize-1); /* find in left half */
 }
}

intmain() {

intn[] = { 3, 7, 8, 1, 2, 5, 6, 9 };

/* should be 7 */
printf("%d\n", findKthLargest(n, sizeof(n) / sizeof(n[0]), 3));

return0;
}