如何在两个排序数组的并集中找到第k个最小元素？

Question

这是一个家庭作业问题.他们说,这需要O(logN + logM)地方N和M是数组的长度.

让我们命名的数组a和b.显然我们可以忽略所有a[i]和b[i]i> k.
首先,让我们来比较一下a[k/2]和b[k/2].让b[k/2]> a[k/2].因此我们也可以丢弃所有b[i],其中i> k/2.

现在我们拥有所有a[i],我<k和所有b[i],其中我<k/2找到答案.

你下一步怎么做？

Answer 1

我希望我没有回答你的作业,因为问这个问题已经有一年多了.这是一个尾递归解决方案,它将采用log(len(a)+ len(b))时间.

假设:输入是正确的.即k在[0,len(a)+ len(b)]的范围内

基本情况:

• 如果其中一个数组的长度为0,则答案是第二个数组的第k个元素.

减少步骤:

• 如果中间指数a+中间指数b小于k
  • 如果mid元素a大于mid元素b,我们可以忽略上半部分b,调整k.
  • 否则忽略前半部分a,调整k.
• 否则,如果k小于和的中间指数之a和b:
  • 如果mid元素a大于mid元素b,我们可以放心地忽略下半部分a
  • 否则我们可以忽略下半场 b

码:

def kthlargest(arr1, arr2, k):
    if len(arr1) == 0:
        return arr2[k]
    elif len(arr2) == 0:
        return arr1[k]

    mida1 = len(arr1)/2
    mida2 = len(arr2)/2
    if mida1+mida2<k:
        if arr1[mida1]>arr2[mida2]:
            return kthlargest(arr1, arr2[mida2+1:], k-mida2-1)
        else:
            return kthlargest(arr1[mida1+1:], arr2, k-mida1-1)
    else:
        if arr1[mida1]>arr2[mida2]:
            return kthlargest(arr1[:mida1], arr2, k)
        else:
            return kthlargest(arr1, arr2[:mida2], k)

请注意,我的解决方案是在每次调用中创建较小数组的新副本,只需在原始数组上传递开始和结束索引即可轻松消除.

Answer 2

你已经拥有它,继续前进!并注意索引......

为了简化一点,我假设N和M都是> k,所以这里的复杂度是O(log k),即O(log N + log M).

伪代码:

i = k/2
j = k - i
step = k/4
while step > 0
    if a[i-1] > b[j-1]
        i -= step
        j += step
    else
        i += step
        j -= step
    step /= 2

if a[i-1] > b[j-1]
    return a[i-1]
else
    return b[j-1]

对于演示,你可以使用循环不变i + j = k,但我不会做你所有的功课:)

Answer 3

很多人回答这个问题的"第k个最小元素来自两个排序数组"的问题,但通常只有一般的想法,而不是明确的工作代码或边界条件分析.

在这里,我想用我正确工作的Java代码帮助一些新手理解的方式仔细详细说明.A1并且A2是两个分类的升序数组,分别具有size1和size2作为长度.我们需要从这两个数组的并集中找到第k个最小元素.在这里我们合理地假设(k > 0 && k <= size1 + size2),这意味着A1并且A2不能都是空的.

首先,让我们用慢速O(k)算法来解决这个问题.方法是比较两个数组的第一个元素,A1[0]和A2[0].拿小一点,A1[0]放到我们的口袋里.然后比较A1[1]有A2[0],等等.重复此动作,直到我们的口袋到达k元素.非常重要:在第一步中,我们只能A1[0]在口袋里承诺.我们不能包含或排除A2[0]!!!

以下O(k)代码在正确答案之前为您提供一个元素.在这里,我用它来展示我的想法,并分析边界条件.在这之后我有正确的代码:

private E kthSmallestSlowWithFault(int k) {
    int size1 = A1.length, size2 = A2.length;

    int index1 = 0, index2 = 0;
    // base case, k == 1
    if (k == 1) {
        if (size1 == 0) {
            return A2[index2];
        } else if (size2 == 0) {
            return A1[index1];
        } else if (A1[index1].compareTo(A2[index2]) < 0) {
            return A1[index1];
        } else {
            return A2[index2];
        }
    }

    /* in the next loop, we always assume there is one next element to compare with, so we can
     * commit to the smaller one. What if the last element is the kth one?
     */
    if (k == size1 + size2) {
        if (size1 == 0) {
            return A2[size2 - 1];
        } else if (size2 == 0) {
            return A1[size1 - 1];
        } else if (A1[size1 - 1].compareTo(A2[size2 - 1]) < 0) {
            return A1[size1 - 1];
        } else {
            return A2[size2 - 1];
        }
    }

    /*
     * only when k > 1, below loop will execute. In each loop, we commit to one element, till we
     * reach (index1 + index2 == k - 1) case. But the answer is not correct, always one element
     * ahead, because we didn't merge base case function into this loop yet.
     */
    int lastElementFromArray = 0;
    while (index1 + index2 < k - 1) {
        if (A1[index1].compareTo(A2[index2]) < 0) {
            index1++;
            lastElementFromArray = 1;
            // commit to one element from array A1, but that element is at (index1 - 1)!!!
        } else {
            index2++;
            lastElementFromArray = 2;
        }
    }
    if (lastElementFromArray == 1) {
        return A1[index1 - 1];
    } else {
        return A2[index2 - 1];
    }
}

最强大的想法是,在每个循环中,我们总是使用基本案例方法.在提交到当前最小元素之后,我们离目标更近一步:第k个最小元素.永远不要跳到中间,让自己迷茫和迷失!

通过观察上面的代码库情况k == 1, k == size1+size2,并与之结合,A1并且A2不能都是空的.我们可以将逻辑转化为更简洁的风格.

这是一个缓慢但正确的工作代码:

private E kthSmallestSlow(int k) {
    // System.out.println("this is an O(k) speed algorithm, very concise");
    int size1 = A1.length, size2 = A2.length;

    int index1 = 0, index2 = 0;
    while (index1 + index2 < k - 1) {
        if (size1 > index1 && (size2 <= index2 || A1[index1].compareTo(A2[index2]) < 0)) {
            index1++; // here we commit to original index1 element, not the increment one!!!
        } else {
            index2++;
        }
    }
    // below is the (index1 + index2 == k - 1) base case
    // also eliminate the risk of referring to an element outside of index boundary
    if (size1 > index1 && (size2 <= index2 || A1[index1].compareTo(A2[index2]) < 0)) {
        return A1[index1];
    } else {
        return A2[index2];
    }
}

现在我们可以尝试在O(log k)运行更快的算法.同样地,比较A1[k/2]有A2[k/2]; 如果A1[k/2]是小的,那么所有从元素A1[0]到A1[k/2]应该在我们的口袋里.我们的想法是不仅仅在每个循环中提交一个元素; 第一步包含k/2元素.同样,我们也不能包含或排除A2[0]到A2[k/2]反正.所以在第一步中,我们不能超过k/2元素.对于第二步,我们不能超过k/4元素......

在每一步之后,我们更接近第k个元素.同时每一步都变得越来越小,直到我们到达(step == 1),这是(k-1 == index1+index2).然后我们可以再次参考简单而强大的基础案例.

这是正确的代码:

private E kthSmallestFast(int k) {
    // System.out.println("this is an O(log k) speed algorithm with meaningful variables name");
    int size1 = A1.length, size2 = A2.length;

    int index1 = 0, index2 = 0, step = 0;
    while (index1 + index2 < k - 1) {
        step = (k - index1 - index2) / 2;
        int step1 = index1 + step;
        int step2 = index2 + step;
        if (size1 > step1 - 1
                && (size2 <= step2 - 1 || A1[step1 - 1].compareTo(A2[step2 - 1]) < 0)) {
            index1 = step1; // commit to element at index = step1 - 1
        } else {
            index2 = step2;
        }
    }
    // the base case of (index1 + index2 == k - 1)
    if (size1 > index1 && (size2 <= index2 || A1[index1].compareTo(A2[index2]) < 0)) {
        return A1[index1];
    } else {
        return A2[index2];
    }
}

如果(index1+index2)跳过k-1,有些人可能会担心怎么办？我们可以错过基本案例(k-1 == index1+index2)吗？这不可能.你可以加0.5 + 0.25 + 0.125 ......,你永远不会超过1.

当然,将上面的代码转换为递归算法非常容易:

private E kthSmallestFastRecur(int k, int index1, int index2, int size1, int size2) {
    // System.out.println("this is an O(log k) speed algorithm with meaningful variables name");

    // the base case of (index1 + index2 == k - 1)
    if (index1 + index2 == k - 1) {
        if (size1 > index1 && (size2 <= index2 || A1[index1].compareTo(A2[index2]) < 0)) {
            return A1[index1];
        } else {
            return A2[index2];
        }
    }

    int step = (k - index1 - index2) / 2;
    int step1 = index1 + step;
    int step2 = index2 + step;
    if (size1 > step1 - 1 && (size2 <= step2 - 1 || A1[step1 - 1].compareTo(A2[step2 - 1]) < 0)) {
        index1 = step1;
    } else {
        index2 = step2;
    }
    return kthSmallestFastRecur(k, index1, index2, size1, size2);
}

希望以上分析和Java代码可以帮助您理解.但永远不要把我的代码复制为你的作业!干杯;)

Answer 4

这是@ lambdapilgrim解决方案的C++迭代版本(参见那里算法的解释):

#include <cassert>
#include <iterator>

template<class RandomAccessIterator, class Compare>
typename std::iterator_traits<RandomAccessIterator>::value_type
nsmallest_iter(RandomAccessIterator firsta, RandomAccessIterator lasta,
               RandomAccessIterator firstb, RandomAccessIterator lastb,
               size_t n,
               Compare less) {
  assert(issorted(firsta, lasta, less) && issorted(firstb, lastb, less));
  for ( ; ; ) {
    assert(n < static_cast<size_t>((lasta - firsta) + (lastb - firstb)));
    if (firsta == lasta) return *(firstb + n);
    if (firstb == lastb) return *(firsta + n);

    size_t mida = (lasta - firsta) / 2;
    size_t midb = (lastb - firstb) / 2;
    if ((mida + midb) < n) {
      if (less(*(firstb + midb), *(firsta + mida))) {
        firstb += (midb + 1);
        n -= (midb + 1);
      }
      else {
        firsta += (mida + 1);
        n -= (mida + 1);
      }
    }
    else {
      if (less(*(firstb + midb), *(firsta + mida)))
        lasta = (firsta + mida);
      else
        lastb = (firstb + midb);
    }
  }
}

它适用于所有0 <= n < (size(a) + size(b))索引并且具有O(log(size(a)) + log(size(b)))复杂性.

例

#include <functional> // greater<>
#include <iostream>

#define SIZE(a) (sizeof(a) / sizeof(*a))

int main() {
  int a[] = {5,4,3};
  int b[] = {2,1,0};
  int k = 1; // find minimum value, the 1st smallest value in a,b

  int i = k - 1; // convert to zero-based indexing
  int v = nsmallest_iter(a, a + SIZE(a), b, b + SIZE(b),
                         SIZE(a)+SIZE(b)-1-i, std::greater<int>());
  std::cout << v << std::endl; // -> 0
  return v;
}