2

Actually, I am teaching myself algorithm and here I am trying to solve this problem which is the following:

We have an array of n positive integers in an arbitrary order and we have k which is k>=1 to n. The question is to output k smallest odd integers. If the number of odd integers in A is less than k, we should report all odd integers. For example, if A = [2, 17, 3, 10, 28, 5, 9, 4, 12,13, 7] and k = 3, the output should be 3, 5, 9. I want to solve this problem in O(n) time.

My current solution is to have another array with only odd numbers and then I apply this algorithm which is by finding the median and divide the list into L, Median , Right and compare the k as the following: 

If |L|<k<= (|L|+|M|) Return the median 
else if K<|L|, solve the problem recursively on (L)
else work on (R, k- (|L|+|M|)

Any help is appreciated.

Faisal
  • 165
  • 1
  • 10
  • 3
    build min heap of the odd numbers (by visiting all numbers). then extract root for k of them – Mitch Wheat Oct 19 '13 at 10:33
  • 2
    http://en.wikipedia.org/wiki/Quickselect – Karoly Horvath Oct 19 '13 at 12:15
  • @Mitch - for a binary min-heap, that's an O(n log n) solution because the heap insertions are O(log n) in the current heap size. The solution is to only allow the heap to grow to size k - on each insert, if the heap size exceeds k, discard the largest item. To handle that efficiently, you need a max heap. When you extract your solution, you extract the items in the reverse of the order you need them but that shouldn't be a problem. –  Oct 19 '13 at 14:03
  • @Mitch - that said, I *think* either binomial heaps or fibonacci heaps give amortized O(1) insertions (I'd have to look them up again to know which) and that's enough for your solution, provided you're OK with using O(n) rather than O(k) auxiliary space to build the heap. –  Oct 19 '13 at 14:07

1 Answers1

2

Assuming the output can be in any order:

Create a separate array with only odd numbers.

Use a selection algorithm to determine the k-th item. One such algorithm is quickselect (which runs in O(n) on average), which is related to quicksort - it partitions the array by some pivot, and then recursively goes to one of the partitioned sides, based on the sizes of each. See this question for more details.

Since quickselect partitions the input, you will be able to output the results directly after running this algorithm (as Karoly mentioned).

Both of the above steps take O(n), thus the overall running time is O(n).

If you need the output in ascending order:

If k = n, and all the numbers are odd, then an O(n) solution to this would be an O(n) sorting algorithm, but no-one knows of such an algorithm.

To anyone who's considering disagreeing, saying that some non-comparison-based sort is O(n) - it's not, each of these algorithms have some other factor in the complexity, such as the size of the numbers.

The best you can do here, with unbounded numbers, is to use the approach suggested in Proger's answer (O(n + k log n)), or iterate through the input, maintaining a heap of the k smallest odd numbers (O(n log k)).

Community
  • 1
  • 1
Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
  • 1
    quickselect already partitioned the input. there's no need to go through again... because of that, there's also no need to worry about duplicates. – Karoly Horvath Oct 19 '13 at 13:03
  • @Faisal After extracting all odd integers, just compare the number of integers extracted with `k` - if `k` is greater or they are equal, just output the numbers. – Bernhard Barker Oct 19 '13 at 13:46