[LeetCode] Find the k-th Smallest Element in the Union of Two Sorted Arrays
Question:
Given two sorted arrays A, B of size m and n respectively. Find the k-th smallest element in the union of A and B. You can assume that there are no duplicate elements.
http://leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html
A special case: Median of two sorted arrays
https://oj.leetcode.com/problems/median-of-two-sorted-arrays/
http://leetcode.com/2011/03/median-of-two-sorted-arrays.html
A Binary Search solution:
Given two sorted arrays A, B of size m and n respectively. Find the k-th smallest element in the union of A and B. You can assume that there are no duplicate elements.
http://leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html
A special case: Median of two sorted arrays
https://oj.leetcode.com/problems/median-of-two-sorted-arrays/
http://leetcode.com/2011/03/median-of-two-sorted-arrays.html
// Option A: Two pointers
//
public int kMin(int[] A, int[] B, int k)
{
int a = 0; // [0, A.length - 1]
int b = 0; // [0, B.length - 1]
int r = -1;
for (int i = 0 ; i = A.length)
return Integer.MIN_VALUE;
return A[i];
}A Binary Search solution:
// Given A[i] and B[j]
// If B[j-1] = A.length ? Integer.MAX_VALUE : A[i];
int Bj_1 = j <= 0 ? Integer.MIN_VALUE : B[j - 1];
int Bj = j >= B.length ? Integer.MAX_VALUE : B[j];
if (Bj_1