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 >>> 1];
  110.             double mid2 = b[lo2 + hi2 - 1 >>> 1];
  111.  
  112.             if (mid1 > mid2) {
  113.                 // swap(a, b); swap(lo1, lo2); swap(hi1, hi2);
  114.                 double[] arraySwap = a; a = b; b = arraySwap;
  115.                 int swap = lo1; lo1 = lo2; lo2 = swap;
  116.                 swap = hi1; hi1 = hi2; hi2 = swap;
  117.             } else if (a[lo1 + hi1 >>> 1] == b[lo2 + hi2 - 1 >>> 1]) {
  118.                 return a[lo1 + hi1 >>> 1];
  119.             } else if (a[lo1 + hi1 - 1 >>> 1] == b[lo2 + hi2 >>> 1]) {
  120.                 return a[lo1 + hi1 >>> 1];
  121.             }
  122.             int cutLength = hi1 - lo1 - 1 >>> 1;
  123.             lo1 += cutLength;
  124.             hi2 -= cutLength;
  125.         }
  126.  
  127.         if (hi1 - lo1 == 1) {
  128.             return (a[lo1] + b[lo2]) / 2;
  129.         } else {
  130.             assert hi1 - lo1 == 2;
  131.             // [a0, a1] [b0, b1] case
  132.             // possible merged arrays:
  133.             //   a0 < b0
  134.             //   [a0, a1, b0, b1] mid = avg(a1, b0) -- a1 < b0 < b1
  135.             //   [a0, b0, a1, b1] mid = avg(a1, b0) -- a1 < b1
  136.             //   [a0, b0, b1, a1] mid = avg(b1, b0) -- a1 > b1
  137.             //   
  138.             //   a0 > b0
  139.             //   [b0, a0, b1, a1] mid = avg(a0, b1) -- a1 > b1
  140.             //   [b0, a0, a1, b1] mid = avg(a0, a1) -- a1 < b1
  141.             //   [b0, b1, a0, a1] mid = avg(a0, b1) -- a1 > a0 > b1
  142.             return (max(a[lo1], b[lo2])
  143.                     + min(a[lo1 + 1], b[lo2 + 1])) / 2;
  144.         }
  145.     }
  146.  
  147.     /**
  148.      * A linear solution of the same problem but now with
  149.      * not necesserily equal-length sorted arrays.
  150.      * @param a a sorted array
  151.      * @param b a sorted array
  152.      */
  153.     static double medianTwoDifferentSizeArraysLinear(double[] a,
  154.             double[] b) {
  155.         assert isSorted(a) && isSorted(b);
  156.  
  157.         // if n := len(a) + len(b) is even, then the median of the
  158.         // merged array equals to avg(mrgd[mid - 1], mrgd[mid])
  159.         //
  160.         // otherwise the median is just mrgd[mid]
  161.         final int n = a.length + b.length;
  162.         int mid = n >>> 1;
  163.         double median1 = Double.NaN, median2 = Double.NaN;
  164.         // a and b iterators respectively
  165.         int i = 0, j = 0;
  166.  
  167.         for (int k = 0; k < mid + 1; k++) {
  168.             median1 = median2;
  169.             if (j == b.length || i < a.length && a[i] < b[j]) {
  170.                 median2 = a[i];
  171.                 i++;
  172.             } else {
  173.                 median2 = b[j];
  174.                 j++;
  175.             }
  176.         }
  177.  
  178.         if (n % 2 == 0) {
  179.             return (median1 + median2) / 2;
  180.         } else {
  181.             return median2;
  182.         }
  183.     }
  184.  
  185.     /**
  186.      * Computes the median of two sorted not necessarily equal
  187.      * length arrays. Runs in logarithmic time and does not
  188.      * require any extra space.
  189.      */
  190.     static double medianTwoDifferentSizeArrays(double[] a, double[] b) {
  191.         assert isSorted(a) && isSorted(b);
  192.  
  193.         int lo1 = 0, hi1 = a.length;
  194.         int lo2 = 0, hi2 = b.length;
  195.  
  196.         while (hi1 - lo1 > 2 && hi2 - lo2 > 2) {
  197.             double median1 = a[lo1 + hi1 - 1 >>> 1];
  198.             double median2 = b[lo2 + hi2 - 1 >>> 1];
  199.  
  200.             if (median1 > median2) {
  201.                 // swap(a, b); swap(lo1, lo2); swap(hi1, hi2);
  202.                 double[] arraySwap = a; a = b; b = arraySwap;
  203.                 int swap = lo1; lo1 = lo2; lo2 = swap;
  204.                 swap = hi1; hi1 = hi2; hi2 = swap;
  205.             } else if (a[lo1 + hi1 >>> 1] == b[lo2 + hi2 - 1 >>> 1]) {
  206.                 return a[lo1 + hi1 >>> 1];
  207.             } else if (a[lo1 + hi1 - 1 >>> 1] == b[lo2 + hi2 >>> 1]) {
  208.                 return a[lo1 + hi1 - 1 >>> 1];
  209.             }
  210.             // -1 to cut [a0, a1, a2, a3] to [a1, a2, a3]
  211.             // not to just [a2, a3]
  212.             int cutLength = min((hi1 - lo1 - 1) >>> 1,
  213.                     (hi2 - lo2 - 1) >>> 1);
  214.             lo1 += cutLength;
  215.             hi2 -= cutLength;
  216.         }
  217.         return medianBaseCase(a, lo1, hi1, b, lo2, hi2);
  218.     }
  219.  
  220.     /**
  221.      * A method designed to handle the base cases when calculating
  222.      * the median of two sorted arrays.
  223.      */
  224.     private static double medianBaseCase(
  225.             double[] a, int lo1, int hi1,
  226.             double[] b, int lo2, int hi2) {
  227.         assert hi1 - lo1 <= 2 || hi2 - lo2 <= 2;
  228.         assert isSorted(a, lo1, hi1) && isSorted(b, lo2, hi2);
  229.         assert rangeCheck(a, lo1, hi1) && rangeCheck(a, lo1, hi1);
  230.  
  231.         if (hi1 - lo1 > hi2 - lo2) {
  232.             // swap(a, b); swap(lo1, lo2); swap(hi1, hi2);
  233.             double[] arraySwap = a; a = b; b = arraySwap;
  234.             int swap = hi1; hi1 = hi2; hi2 = swap;
  235.             swap = lo1; lo1 = lo2; lo2 = swap;
  236.         }
  237.  
  238.         int aLength = hi1 - lo1;
  239.         int bLength = hi2 - lo2;
  240.  
  241.         if (aLength == 0 && bLength == 0) {
  242.             return Double.NaN;
  243.         }
  244.         if (aLength == 2 && bLength == 2) {
  245.             return twoTwoMedian(a, lo1, hi1, b, lo2, hi2);
  246.         }
  247.         if (aLength == 1 && bLength == 1) {
  248.             return (a[lo1] + b[lo2]) / 2;
  249.         }
  250.         if (aLength == 1 && bLength == 2) {
  251.             return oneTwoMedian(a, lo1, hi1, b, lo2, hi2);
  252.         }
  253.  
  254.         int mid = (lo2 + hi2) >>> 1;
  255.         if (aLength == 0) {
  256.             if (bLength % 2 == 0) {
  257.                 return (b[mid - 1] + b[mid]) / 2;
  258.             } else {
  259.                 return b[mid];
  260.             }
  261.         }
  262.         if (aLength == 1) {
  263.             // [1, 3, 5, 7] -> (insert 2, 4, 6)
  264.             // [1, 2*, 3, 5, 7], [1, 3, 4*, 5, 7] or [1, 3, 5, 6*, 7]
  265.             if (bLength % 2 == 0) {
  266.                 if (a[lo1] < b[mid - 1]) {
  267.                     return b[mid - 1];
  268.                 } else if (b[mid - 1] < a[lo1] && a[lo1] < b[mid]) {
  269.                     return a[lo1];
  270.                 } else {
  271.                     return b[mid];
  272.                 }
  273.             // [1, 3, 5] -> (insert 0, 2, 4, 6)
  274.             // [0*, 1, 3, 5], [1, 2*, 3, 5],
  275.             // [1, 3, 4*, 5], [1, 3, 5, 6*]
  276.             } else {
  277.                 if (a[lo1] < b[mid - 1]) {
  278.                     return (b[mid - 1] + b[mid]) / 2;
  279.                 } else if (b[mid - 1] < a[lo1] && a[lo1] < b[mid + 1]) {
  280.                     return (b[mid] + a[lo1]) / 2;
  281.                 } else {
  282.                     return (b[mid] + b[mid + 1]) / 2;
  283.                 }
  284.             }
  285.         }
  286.         if (aLength == 2) {
  287.             // [2, 5, 8, 11] -> (insert [0, 1], [3, 4], [6, 7]...)
  288.             // [0*, 1*, 2, 5, 8, 11], [2, 3*, 4*, 5, 8, 11]
  289.             // [2, 5, 6*, 7*, 8, 11], [2, 5, 8, 9*, 10*, 11]
  290.             // [2, 5, 8, 11, 12*, 13*]
  291.             if (bLength % 2 == 0) {
  292.                 if (a[lo1 + 1] < b[mid - 2]) {
  293.                     return (b[mid - 2] + b[mid - 1]) / 2;
  294.                 } else if (b[mid + 1] < a[lo1]) {
  295.                     return (b[mid] + b[mid + 1]) / 2;
  296.                 } else {
  297.                     return twoTwoMedian(a, lo1, hi1, b, mid - 1, mid + 1);
  298.                 }
  299.             // [2, 5, 8] -> (insert [0, 1], [3, 4], [6, 7], [9, 10])
  300.             // [0*, 1*, 2, 5, 8], [2, 3*, 4*, 5, 8]
  301.             // [2, 5, 6*, 7*, 8], [2, 5, 8, 9*, 10*]
  302.             } else {
  303.                 if (a[lo1 + 1] < b[mid - 1]) {
  304.                     return b[mid - 1];
  305.                 } else if (b[mid + 1] < a[lo1]) {
  306.                     return b[mid + 1];
  307.                 } else {
  308.                     return oneTwoMedian(b, mid, mid + 1, a, lo1, hi1);
  309.                 }
  310.             }
  311.         }
  312.         return Double.NaN;
  313.     }
  314.  
  315.     /**
  316.      * Returns the k-th largest element among two sorted arrays
  317.      * a and b. Runs in linear time.
  318.      */
  319.     static double kthLargestLinear(double[] a, double[] b, int k) {
  320.         assert isSorted(a) && isSorted(b);
  321.  
  322.         if (k < 0 || k >= a.length + b.length) {
  323.             throw new IndexOutOfBoundsException(String.format(
  324.                 "Got: len(a) = %d, len(b) = %d, k = %d",
  325.                 a.length, b.length, k
  326.             ));
  327.         }
  328.  
  329.         double last = Double.NaN;
  330.         int indexA = 0, indexB = 0;
  331.         for (int i = 0; i < k + 1; i++) {
  332.             if (indexB == b.length
  333.                     || indexA < a.length && a[indexA] < b[indexB]) {
  334.                 last = a[indexA];
  335.                 indexA++;
  336.             } else {
  337.                 last = b[indexB];
  338.                 indexB++;
  339.             }
  340.         }
  341.         return last;
  342.     }
  343.  
  344.     /**
  345.      * Finds the k-th largest element among two sorted arrays.
  346.      * Runs in O(lgk) time.
  347.      */
  348.     static double kthLargest(double[] a, double[] b, int k) {
  349.         assert isSorted(a) && isSorted(b);
  350.  
  351.         if (k < 0 || k >= a.length + b.length) {
  352.             throw new IndexOutOfBoundsException(String.format(
  353.                 "Got: len(a) = %d, len(b) = %d, k = %d",
  354.                 a.length, b.length, k
  355.             ));
  356.         }
  357.  
  358.         int lo1 = 0, hi1 = a.length;
  359.         int lo2 = 0, hi2 = b.length;
  360.  
  361.         while (k >= 0) {
  362.             // in case one of the arrays is empty, return the k-th
  363.             // element of the non-empty array
  364.             if (lo1 == hi1) {
  365.                 return b[lo2 + k];
  366.             }
  367.             if (lo2 == hi2) {
  368.                 return a[lo1 + k];
  369.             }
  370.             // (at this point each array contains at least 1 element)
  371.             if (k == 0) {
  372.                 return min(a[lo1], b[lo2]);
  373.             }
  374.             // keep the reference to the smaller array in the variable `a`
  375.             // for simplicity
  376.             if (hi1 - lo1 > hi2 - lo2) {
  377.                 // swap(a, b); swap(lo1, lo2); swap(hi1, hi2);
  378.                 double[] arraySwap = a; a = b; b = arraySwap;
  379.                 int swap = lo1; lo1 = lo2; lo2 = swap;
  380.                 swap = hi1; hi1 = hi2; hi2 = swap;
  381.             }
  382.             // if one of the arrays' length is <= k + 1 / 2, it might be
  383.             // the case that all the elements from this array are
  384.             // less than the k-th largest element of the two arrays
  385.             if (hi1 - lo1 <= (k + 1) / 2) {
  386.                 if (a[hi1 - 1] < b[lo2 + k  - (hi1 - lo1)]) {
  387.                     return b[lo2 + k  - (hi1 - lo1)];
  388.                 } else {
  389.                     lo2 += (k + 1) / 2;
  390.                     k -= (k + 1) / 2;
  391.                 }
  392.             } else {
  393.                 if (a[lo1 + k / 2] == b[lo2 + k / 2]) {
  394.                     return a[lo1 + k / 2];
  395.                 }
  396.                 if (a[lo1 + k / 2] > b[lo2 + k / 2]) {
  397.                     // swap(a, b); swap(lo1, lo2); swap(hi1, hi2);
  398.                     double[] arraySwap = a; a = b; b = arraySwap;
  399.                     int swap = lo1; lo1 = lo2; lo2 = swap;
  400.                     swap = hi1; hi1 = hi2; hi2 = swap;
  401.                 }
  402.                 lo1 += (k + 1) / 2;
  403.                 k -= (k + 1) / 2;
  404.             }    
  405.         }
  406.         return Double.NaN;
  407.     }
  408.  
  409.     private static double oneTwoMedian(
  410.             double[] a, int lo1, int hi1,
  411.             double[] b, int lo2, int hi2) {
  412.         assert hi1 - lo1 == 1 && hi2 - lo2 == 2;
  413.         // return a0 + b0 + b1 - min(a0, b0) - max(a0, b1);
  414.         // return max(a0, b0) + min(0, b1 - a0);
  415.         return max(a[lo1], b[lo2]) + min(0, b[lo2 + 1] - a[lo1]);
  416.     }
  417.  
  418.     private static double twoTwoMedian(
  419.             double[] a, int lo1, int hi1,
  420.             double[] b, int lo2, int hi2) {
  421.         assert hi1 - lo1 == 2 && hi2 - lo2 == 2;
  422.  
  423.         return (max(a[lo1], b[lo2]) + min(a[lo1 + 1], b[lo2 + 1])) / 2;
  424.     }
  425.  
  426.     /**
  427.      * Checks if the array of doubles is sorted.
  428.      * Used solely for assertions tests.
  429.      */
  430.     private static boolean isSorted(double[] a, int lo, int hi) {
  431.         assert rangeCheck(a, lo, hi)
  432.             : String.format("len(a) = %d, lo = %d, hi = %d",
  433.                 a.length, lo, hi);
  434.  
  435.         for (int i = lo; i < hi - 1; i++) {
  436.             if (a[i] > a[i + 1]) {
  437.                 return false;
  438.             }
  439.         }
  440.         return true;
  441.     }
  442.  
  443.     private static boolean isSorted(double[] a) {
  444.         return isSorted(a, 0, a.length);
  445.     }
  446.  
  447.     /**
  448.      * Checks if the specified interval belongs to the array.
  449.      * Returns false in case it does not, the interval is defined
  450.      * incorrectly (empty intervals are acceptable) or a == null.
  451.      *
  452.      * Used solely for assertions tests.
  453.      */
  454.     private static boolean rangeCheck(double[] a, int lo, int hi) {
  455.         if (a == null) {
  456.             return false;
  457.         } else if (lo < 0 || lo >= a.length && lo != 0
  458.                 || hi < 0 || hi > a.length) {
  459.             return false;
  460.         } else if (lo > hi) {
  461.             return false;
  462.         }
  463.         return true;
  464.     }
  465.  
  466.     public static void main(String[] args) {
  467.         double[] a = { 0, 2, 4, 6, 8 };
  468.         double[] b = { 1, 3, 5, 7, 9 };
  469.         int k = 4;
  470.         System.out.println(medianTwoArraysLinear(a, b));
  471.         System.out.println(medianTwoArrays(a, b));
  472.  
  473.         System.out.println(medianTwoDifferentSizeArraysLinear(a, b));
  474.         System.out.println(medianTwoDifferentSizeArrays(a, b));
  475.  
  476.         System.out.println(kthLargestLinear(a, b, k));
  477.         System.out.println(kthLargest(a, b, k));
  478.     }
  479. }
Success #stdin #stdout 0.09s 32976KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4.5
4.5
4.5
4.5
4.0
4.0
https://ideone.com/Z5I9f3
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!