Pseudocode: 1. Choose a pivot element from amongst the elements in the arrays. 2. Partition each array into sets with elements lesser and greater than the pivot element. 3. Compute the rank of the pivot element by adding the number of elements lesser than the pivot in each of the arrays. If the rank of the pivot - r - is the required rank - k - then done. If r>k you need to look in the subarrays of smaller elements. If r < k, you need to look in the subarrays of larger elements for (k-r) th ranked element.
If the arrays are sorted than the partitioning takes logarithm (in size of array) time. So the overall expected time taken will be O((log n)^2), where n is the size of the arrays (I assume the number of arrays is fixed). Some intuition can be used to select the pivot element wisely based on the information of distribution of elements. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
