从两个已排序的数组中找到第k小的元素

Question

我已经实现了一个可行的函数来完成这个任务，但效率不是很高，因为每次调用都会复制一份新的副本。我尝试将其转换为仅使用a_start、a_end、b_start、b_end，但无法适用于所有情况。请问怎样才能够让它接受a和b数组的起始和结束指针呢？我尝试了以下方法并修改了k-i-1和k-j-1，以便仅使用k，但没有成功。

int m = a_right-a_left, n=b_right-b_left;
int i = (a_left+a_right)/2;
or int i = (int)((m* (k-1)) / (m+n) ); 

以下是使用每次调用时的新数组副本的工作代码。

public static int kthSmallest(int[] a, int[] b,  int k) {
    if (a.length==0)
        return b[k-1];
    else if (b.length==0)
        return a[k-1];
    else if (b.length<a.length)
        return kthSmallest(b, a, k);

        // make sure i + j = k - 1
        int m = a.length, n=b.length;
        int i = (int)((double)m / (m+n) * (k-1));  // make sure i won't be out of bounds
        int j = k - 1 - i;
        int bj_1 = 0, ai_1 = 0;

        if (i==0) {  ai_1 = Integer.MIN_VALUE; } // in case i = 0, outOfBound
        else {  ai_1 = a[i-1]; }
        if (j==0) { bj_1 = Integer.MIN_VALUE; } // in case j = 0, outOfBound
        else {  bj_1 = b[j-1]; }

        if (bj_1 < a[i] && a[i] < b[j]) // kth smallest found, b[j-1] < a[i] < b[j]
            return a[i];
        if (ai_1 < b[j] && b[j] < a[i]) // kth smallest found, a[i-1] < b[j] < a[i]
            return b[j];

        if ( a[i] < b[j] ) // if true, exclude a's lower bound (if 2 arrays merged, a's lower bound must
            // reside before kth smallest, so also update k. 
            // also exclude b's upper bound, since they are all greater than kth element.
            return kthSmallest(Arrays.copyOfRange(a, i+1, a.length), Arrays.copyOfRange(b, 0, j), k-i-1);
        else
            return kthSmallest(Arrays.copyOfRange(a, 0, i), Arrays.copyOfRange(b, j+1, b.length), k-j-1);
}

- user3216886

---

可能是重复的问题：如何在两个已排序数组的并集中找到第k小的元素？ - Raymond Chen

我已经查看过了，没有找到对我的问题的答案。 - user3216886

在C++中，可以直接增加数组的起始指针，但在Java中不可能。 - user3216886

使用数组索引而不是指针。 - jfs

提交作业时别忘了引用 Stack Overflow，我们不希望你被指控作弊。 - Raymond Chen

Answer 1

这是一个关于编程的问题，涉及到寻找两个已排序数组中第k小的元素。此答案提供了一个时间复杂度为O(log a.length + log b.length)的算法。以下是该算法从C++递归实现翻译成Java代码的结果：

public static int ksmallest(int[] a, int[] b,
                            int a1, int a2, int b1, int b2,
                            int k) {
    int lena = a2 - a1;
    int lenb = b2 - b1;
    assert (0 <= k && k < (lena + lenb));
    if (lena == 0) {
        return b[b1 + k];
    }
    if (lenb == 0) {
        return a[a1 + k];
    }
    int mida = lena / 2;
    int midb = lenb / 2;
    int ma = a[a1 + mida];
    int mb = b[b1 + midb];
    if ((mida + midb) < k) {
        return (mb < ma) ?
            ksmallest(a, b, a1, a2, b1 + midb + 1, b2, k - (midb + 1)) :
            ksmallest(a, b, a1 + mida + 1, a2, b1, b2, k - (mida + 1));
    }
    else {
        return (mb < ma) ?
            ksmallest(a, b, a1, a1 + mida, b1, b2, k) :
            ksmallest(a, b, a1, a2, b1, b1 + midb, k);
    }
}

这里还有一个时间复杂度相同的C++迭代实现（没有递归）。它可以像递归版本一样移植到Java。

递归版本的健全性检查：

/** concatenate a, b arrays */
public static int[] concatenate(int[] a, int[] b) {
    int lena = a.length;
    int lenb = b.length;
    int[] c = new int[lena + lenb];
    System.arraycopy(a, 0, c, 0, lena);
    System.arraycopy(b, 0, c, lena, lenb);
    return c;
}

public static void main(String[] args) {
    int a[] = {0, 3, 7, 8};
    int b[] = {0, 2, 3};
    int c[] = concatenate(a, b);
    Arrays.sort(c);
    for (int n = 0; n < (a.length + b.length); n++) {
        int k = ksmallest(a, b, 0, a.length, 0, b.length, n);
        if (k != c[n]) {
            System.out.println(n + ": expected " + c[n] + " got " + k);
        }
    }
}

成功时，不会打印任何内容。

- jfs

Answer 2

一个时间复杂度为O(n)且易于理解的算法；

//both arrays are sorted
private int getKthSmallestElement(int[] array1, int[] array2, int k) {
    int elem=-1;
    int index1=0,index2=0;
    while(k != 0 && (index1<array1.length) && (index2 < array2.length))
    {            
        if(array1[index1] < array2[index2])
        {
            index1++;
        }
        else
            index2++;
        k--;         
    }

    if((index1<array1.length) && (index2 < array2.length))
        return array1[index1] > array2[index2] ? array2[index2] :array1[index1] ;
    else
    {
        if(index1 >= array1.length)
        {
            return array2[index2+k]; 
        }
        else{
            return array1[index1+k];            
        }
    }
}

- Dineshkumar

---

这个在k=1（最小元素）时会失败，因为它使用while(k!=0... - kellyfj

Answer 3

与问题中提到的逻辑相同，但稍微更改了一下，以避免为每个调用创建新数组。

//alow, ahigh are used to maintain the size of a array we are using instead 
//of creating a new array. imilarly for blow, bhigh
public static int search(int[] a, int[] b, int alow, int ahigh, int blow, int bhigh, int k){

    if (alow>ahigh) // if "a" array is of zero length, then take kth element from "b"
        return b[blow+k-1];
    else if (blow>bhigh || bhigh-blow == 0) // Similarly, // if "b" array is of zero length, then take kth element from "a"
        return a[alow+k-1];
    else if ((bhigh-blow)<(ahigh-alow)) //always make sure that a's length is lower length
        return search(b, a,blow,bhigh,alow,ahigh, k);

        // make sure i + j = k - 1
        int m = ahigh-alow+1, n=bhigh-blow+1;
        int i = (int)((double)m / (m+n) * (k-1));  // make sure i won't be out of bounds
        int j = Math.min(k - 1 - i,n-1);
        int bj_1 = 0, ai_1 = 0;

        if (i==0) {  ai_1 = Integer.MIN_VALUE; } // in case i = 0, outOfBound
        else {  ai_1 = a[i-1]; }
        if (j==0) { bj_1 = Integer.MIN_VALUE; } // in case j = 0, outOfBound
        else {  bj_1 = b[j-1]; }

        if (bj_1 < a[i] && a[i] < b[j]) // kth smallest found, b[j-1] < a[i] < b[j]
            return a[i];
        if (ai_1 < b[j] && b[j] < a[i]) // kth smallest found, a[i-1] < b[j] < a[i]
            return b[j];

        if ( a[i] < b[j] ) // if true, exclude a's lower bound (if 2 arrays merged, a's lower bound must
            // reside before kth smallest, so also update k. 
            // also exclude b's upper bound, since they are all greater than kth element.
            return search(a, b,alow+i+1,ahigh,   blow,j-1,         k-i-1);
        else
            return search(a,b,alow,  i-1,        blow+j+1,bhigh,   k-j-1);
    }

- Hulk

Answer 4

这里是一个简单的递归解决方案，时间复杂度为O((logn)^2)，而且不需要复制：

public class KthElement {
    public static int binSearch(int[] arr,int low,int high,int key) {
        int mid=0;
        while(high>=low) {
            mid = (high+low)/2;
            if(arr[mid]==key) {
                return(mid);
            }
            else if(arr[mid]<key) {
                low = mid+1;
            }
            else {
                high = mid-1;
            }
        }
        if(arr[mid]>key) {
            return(mid-1);
        }
        return(mid);
    }

    public static int kthElement(int[] arr1,int[] arr2,int s1,int h1,int s2,int h2,int k) {
        int len1 = (h1-s1+1);
        int len2 = (h2-s2+1);
        if(len1<=0) {
            return(arr2[s2+k-1]);
        }
        if(len2<=0) {
            return(arr1[s1+k-1]);
        }

        if(k>(len1+len2)) {
            return(-1);
        }

        int mid = (s1+h1)/2;
        int i = binSearch(arr2,s2,h2,arr1[mid]);
        int size = mid+i-s1-s2+2;
        //System.out.println(mid+" "+i+" "+size);
        if(size==k){
            return(arr1[mid]);
        }
        if(size>k) {
            return(kthElement(arr1, arr2, s1,mid-1, s2,i, k));
        }
        else {
            return(kthElement(arr1, arr2, mid+1,h1,i+1,h2, k-size));
        }

    } 

    public static void main(String[] args) {
        int[] arr1 = {1,3,5,7,9,11,13};
        int[] arr2 = {2,4,6,8,10,12};
        int k = 6;
        System.out.println(k+"th Element : "+kthElement(arr1, arr2,0,arr1.length-1, 0,arr2.length-1, k));
    }

}

- Vikram Bhat

Answer 5

这里是JAVA的迭代解决方案：

O(log A.length + log B.length)时间复杂度

public static int kthsmallest(int []A, int []B, int K){

    int begin = Math.max(0,K-B.length); // binary search begin index
    int end   = Math.min(A.length,K);  // binary search end end index

    while(begin < end){
        // search until mid = k
        int mid = begin +(end-begin)/2;

        if(mid<A.length && K-mid>0 && A[mid]<B[K-mid-1]){
            begin = mid+1;

        }else if( mid > 0 && K-mid <B.length && A[mid-1]>B[K-mid]){
            end = mid;

        }else{
            begin=mid;
            break;
        }
    }

    if(begin ==0){
        return B[K-1];
    }else if(begin == K){
        return A[K-1];
    }else{
        return Math.max(A[begin -1],B[K-begin-1]);
    }
}

- sreeprasad