FindKthSmallest.java

/**
 * Created by linwei on 9/22/16.
 */
public class FindKthSmallest {
    /*
     * Example:
     * 1,2,3,4 and 3,4,5,6,7 k=5, return 4;
     * 1,2,3,4 and 3,4,5,6,7 k=2, return 2;
     */
    public int find(int[] a, int[] b, int k) {
        if (a == null || b == null) return -1;
        if (a.length == 0) return b[k-1];
        if (b.length == 0) return a[k-1];
        if (k > a.length + b.length) return -1;

        int i = 0, j = 0;  // two pointers
        int currentIndex = 0;
        while (i < a.length && j < b.length && currentIndex < k - 1) {
            if (a[i] <= b[j]) {
                i++;
                currentIndex++;  // find the current smallest
            } else {
                j++;
                currentIndex++;
            }
        }
        System.out.println("k: " + k);
        System.out.println("currentIndex: " + currentIndex);
        System.out.println("i: " + i);
        System.out.println("j: " + j);
        if (i != a.length && j != b.length) return Math.min(a[i], b[j]);
        if (i == a.length) {
            // 1,2 and 2,3,4,5,6 k = 5, return 4
            while (currentIndex < k) {
                j++;
                currentIndex++;
            }
            return b[j];

        } else {
            while (currentIndex <k) {
                i++;
                currentIndex++;
            }
            return a[i];
        }


    }
}