How to find Kth smallest number in an array which formed by product of each element of 3 array A,B,C? (Time limit :2s)

Revision en1, by starkkk, 2017-09-05 12:22:53

Here is the full description of the problem

The length of each array A,B and C <= 1000 and K <= min(10^6, na * nb * nc) (na,nb,nc is the length of each array A,B and C)

I have thought that we can run through array A and B to find all the products of A and B in O(n^2) and generate Kth number by multiply that products with element in array C. But I don't know how to exactly generate Kth number in step 2th.

In this problem, the number can be NEGATIVE

Does anyone help me about this or give me your idea how to solve this problem? Thank you!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English starkkk 2017-09-05 12:22:53 715 Initial revision (published)