purist's blog

By purist, history, 3 months ago, In English,

Given an array, we can generate an array which stores all the pairwise absolute difference of elements of original array. How can we find median of this new array. For example : A = {1,2,3,4} then we can generate difference array as G = {1,1,1,2,2,3} then median is 1.can it be done in better than quadratic time? Also what if we don't take absolute value of difference?

 
 
 
 
  • Vote: I like it  
  • +16
  • Vote: I do not like it  

»
3 months ago, # |
  Vote: I like it +16 Vote: I do not like it

N *logN logN approach. - 1. Sort the elements. - 2. Do binary search on median. - 3. For a particular value of median you can check how many pairwise elements will be smaller than the median. You can do this N log N , as you will have do again binary search on array.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Actually it can be done in by using two pointers technique.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How do you check number of pairs smaller than current value using binary search?