Find K Biggest

#include <stdio.h> void k_biggest(int *list, int *new, int n, int k) { int i, j, min; for (i = 0; i < k; i++) // put first k item into new array new[i] = list[i]; for (j = i; j < n; j++) { for (min = 0, i = 1; i < k; i++) { // search the min value in new array if (new[i] < new[min]) min = i; } if (list[j] > new[min]) // if new item larger than min item, replace min by it new[min] = list[j]; } } int main() { int list[15] = {30,1,4,5,2,5,8,0,13,25,6,26,88,3,97}; int new[7]; k_biggest(list, new, 15, 7); int i; for (i = 0; i < 7; i++) printf("%d ", new[i]); }

Note:

1) It has time complexity O(k + (n-k)*k) = O((n-k)*k) in worst case, and O(k + k + (n-k)) = O(n) (need to do a little optimization).

2) A possible optimization is to use a Min Heap to maintain the new array. First, construct a min heap with the first k item, then do removemin() when min value is smaller for n-k time. Therefore, the time complexity is O(k + (n-k)*logk)

page revision: 5, last edited: 23 May 2010 21:53