fork download
copy 
  1. import static java.lang.Math.max;
  2. import static java.lang.Math.min;
  3.  
  4. class KthLargestTwoArrays {
  5.     /**
  6.      * Given two sorted arrays of equal sizes, finds the median of the
  7.      * array that comes out after `a` and `b` being merged. Runs in
  8.      * linear time and does not require any extra space.
  9.      *
  10.      * The algorithm is similar to the arrays merging, but it
  11.      * does not save the merged array, it just iterates through both
  12.      * of them by n+1 items (thus stopping in the middle of an imaginary
  13.      * merged array) and memorizes two consecutive elements. These
  14.      * are the two elements laying exactly in the middle of merged array.
  15.      *
  16.      * (Since the length of the merged array is even, its median
  17.      * is an average value of two elements in the middle.)
  18.      *
  19.      * @param a a sorted array
  20.      * @param b a sorted array
  21.      */
  22.     static double medianTwoArraysLinear(double[] a, double[] b) {
  23.         if (a.length != b.length) {
  24.             throw new IllegalArgumentException(String.format(
  25.                 "Expected: len(a) == len(b)."
  26.                 + " Got: len(a) = %d, len(b) = %d",
  27.                 a.length, b.length
  28.             ));
  29.         }
  30.  
  31.         final int n = a.length;
  32.         int i = 0, j = 0;
  33.         // two consecutive elements of the merged array
  34.         double mid1 = Double.NaN, mid2 = Double.NaN;
  35.         for (int k = 0; k < n + 1; k++) {
  36.             // here we also handle a special case when every element
  37.             // of the first array is smaller than the smallest element
  38.             // of the second array (and vice versa)
  39.             if (j == n || i < n && a[i] < b[j]) {
  40.                 // put the previous value into the buffer
  41.                 mid1 = mid2;
  42.                 mid2 = a[i];
  43.                 i++;
  44.             } else {
  45.                 mid1 = mid2;
  46.                 mid2 = b[j];
  47.                 j++;
  48.             }
  49.         }
  50.         return (mid1 + mid2) / 2;
  51.     }
  52.  
  53.     /**
  54.      * A logarithmic-time algorithm that solves the same problem.
  55.      * The basic idea is to compute the medians of both of the
  56.      * arrays (well, these are not exactly "medians", in case the
  57.      * array length is even, mid = A[n / 2], not the average value):
  58.      *     A = [a1, a2, ..., mid1, ..., an] 
  59.      *     B = [b1, b2, ..., mid2, ..., bn]
  60.      * and after that there are three cases to consider:
  61.      *
  62.      *  - mid1 == mid2, which means (given len(A) == len(B)) that
  63.      *    in every array there are n/2 elemets on the left side
  64.      *    from the mid, so in the merged array mid1 and mid2 would
  65.      *    be on n/2 + n/2 = n and n+1 positions (thus mid1 is the
  66.      *    median of the merged array)
  67.      *
  68.      *  - mid1 &lt; mid2 means that the greatest element of the left
  69.      *    side of the array A (A_left) is at most as large as the
  70.      *    greatest element of B_left. And similarly the smallest
  71.      *    element of B_right is at least as large as the smallest
  72.      *    element of A_right.
  73.      *
  74.      *    This means that the left side of the imaginary merged array
  75.      *    for sure would not end with an element from A_left, and
  76.      *    the right side will not start with an value from B_right.
  77.      *    (It can be easily seen from the example down below, just
  78.      *    follow the steps of the merge algorithm.)
  79.      *
  80.      *    Thus the desired median elements are somewhere in
  81.      *    A_right or B_left. When computing the median we can get rid
  82.      *    of the same amount of elements on the right as on the left side
  83.      *    and the result will not change in case the elements on the left
  84.      *    are smaller than the median, meanwhile elements on the right
  85.      *    are greater. So we can do here: A_left and B_right can be
  86.      *    thrown away leaving us with just A_right and B_left -
  87.      *    now we have the same problem but of half of the size.
  88.      *
  89.      *    Example:
  90.      *    a = [ 1, 2, 3, 4, 8 ]
  91.      *    b = [ 0, 3, 4, 5, 6 ]
  92.      *    Merged: [ 0, 1*, 2*, 3, 3* | 4, 4*, 5, 6, 8* ]
  93.      *    (elements from the first array are marked with asterisks)
  94.      *
  95.      *  - mid1 &gt; mid2 case is handled similarly.  */ 
  96.     static double medianTwoArrays(double[] a, double[] b) {
  97.         if (a.length != b.length) {
  98.             throw new IllegalArgumentException(String.format(
  99.                 "Expected: len(a) == len(b)."
  100.                 + "Got: len(a) = %d, len(b) = %d",
  101.                 a.length, b.length
  102.             ));
  103.         } 
  104.         final int n = a.length;
  105.         int lo1 = 0, hi1 = n; // left subarray
  106.         int lo2 = 0, hi2 = n; // right subarray
  107.  
  108.         while (hi1 - lo1 > 2) {
  109.             double mid1 = a[(lo1 + hi1) >>> 1];
  110.             double mid2 = b[(lo2 + hi2) >>> 1];
  111.  
  112.             if (mid1 > mid2) {
  113.                 double[] arraySwap = a;
  114.                 a = b;
  115.                 b = arraySwap;
  116.  
  117.                 int swap = lo1;
  118.                 lo1 = lo2;
  119.                 lo2 = swap;
  120.  
  121.                 swap = hi1;
  122.                 hi1 = hi2;
  123.                 hi2 = swap;
  124.             } else if (mid1 == mid2) {
  125.                 return mid1;
  126.             }
  127.             lo1 = (lo1 + hi1) >>> 1;
  128.             hi2 = (lo2 + hi2 + 1) >>> 1;
  129.         }
  130.  
  131.         if (hi1 - lo1 == 1) {
  132.             return (a[lo1] + b[lo2]) / 2;
  133.         } else {
  134.             assert hi1 - lo1 == 2;
  135.             // [a0, a1] [b0, b1] case
  136.             // possible merged arrays:
  137.             //   a0 < b0
  138.             //   [a0, a1, b0, b1] mid = avg(a1, b0) -- a1 < b0 < b1
  139.             //   [a0, b0, a1, b1] mid = avg(a1, b0) -- a1 < b1
  140.             //   [a0, b0, b1, a1] mid = avg(b1, b0) -- a1 > b1
  141.             //   
  142.             //   a0 > b0
  143.             //   [b0, a0, b1, a1] mid = avg(a0, b1) -- a1 > b1
  144.             //   [b0, a0, a1, b1] mid = avg(a0, a1) -- a1 < b1
  145.             //   [b0, b1, a0, a1] mid = avg(a0, b1) -- a1 > a0 > b1
  146.             return (max(a[lo1], b[lo2])
  147.                     + min(a[lo1 + 1], b[lo2 + 1])) / 2;
  148.         }
  149.     }
  150.  
  151.     public static void main(String[] args) {
  152.         double[] a = { 1, 12, 15, 26, 38 };
  153.         double[] b = { 2, 13, 17, 30, 45 };
  154.         System.out.println(medianTwoArrays(a, b));
  155.         System.out.println(medianTwoArraysLinear(a, b));
  156.     }
  157. }
Success #stdin #stdout 0.06s 33068KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
16.0
16.0
https://ideone.com/6NxXBH
language:
Java (HotSpot 12)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!