我有2个整数排序数组，如何找到O(logn)时间中的第k个最大项？ - java

采访中有人问我这个问题。我显然可以在O(n)的时间内完成此操作，但是我没有考虑在O(logn)中解决的方法。听起来好像使用了一些分治法，但是我不确定。

参考方案

将两者都截断为大小k。如有必要，让程序在一个或两个数组的末尾想象足够的无穷大，以使它们的大小达到k；这不会影响渐近运行时。 (在实际的实现中，我们可能会做些更有效的事情。)

然后，比较每个数组的第k / 2个元素。如果比较的元素相等，则我们找到第k个元素；否则，让第k / 2'个元素的数组为A，另一个为B。丢掉A的下半部分和B的上半部分，然后递归地找到剩下的第k / 2'个元素。当我们达到k = 1时停止。

在每一步中，保证A的下半部分过小，确保B的上半部分过大。保证剩余的第k / 2个元素大于A的下半部分，因此保证是原始元素的第k个元素。

在Python中的概念验证:

def kth(array1, array2, k):
    # Basic proof of concept. This doesn't handle a bunch of edge cases
    # that a real implementation should handle.
    # Limitations:
    #   Requires numpy arrays for efficient slicing.
    #   Requires k to be a power of 2
    #   Requires array1 and array2 to be of length exactly k
    if k == 1:
        return min(array1[0], array2[0])
    mid = k//2 - 1
    if array1[mid] > array2[mid]:
        array1, array2 = array2, array1
    return kth(array1[k//2:], array2[:k//2], k//2)

我已经测试过了，但是还不多。

Java:正则表达式模式匹配器是否有大小限制？ - java

我的模式类似于OR:“word1 | word2 | word3”我大约有800个字。可能有问题吗？ 参考方案 您仅受记忆和理智的限制。 :)

Java:线程池如何将线程映射到可运行对象 - java

试图绕过Java并发问题，并且很难理解线程池，线程以及它们正在执行的可运行“任务”之间的关系。如果我创建一个有10个线程的线程池，那么我是否必须将相同的任务传递给池中的每个线程，或者池化的线程实际上只是与任务无关的“工人无人机”可用于执行任何任务？无论哪种方式，Executor / ExecutorService如何将正确的任务分配给正确的线程？ 参考方案 …

JAVA:字节码和二进制有什么区别？ - java

java字节代码（已编译的语言，也称为目标代码）与机器代码（当前计算机的本机代码）之间有什么区别？我读过一些书，他们将字节码称为二进制指令，但我不知道为什么。 参考方案 字节码是独立于平台的，在Windows中运行的编译器编译的字节码仍将在linux / unix / mac中运行。机器代码是特定于平台的，如果在Windows x86中编译，则它将仅在Win…

java:继承 - java

有哪些替代继承的方法？ java大神给出的解决方案 有效的Java：偏重于继承而不是继承。 （这实际上也来自“四人帮”）。他提出的理由是，如果扩展类未明确设计为继承，则继承会引起很多不正常的副作用。例如，对super.someMethod()的任何调用都可以引导您通过未知代码的意外路径。取而代之的是，持有对本来应该扩展的类的引用，然后委托给它。这是与Eric…

Java:BigInteger，如何通过OutputStream编写它 - java

我想将BigInteger写入文件。做这个的最好方式是什么。当然，我想从输入流中读取（使用程序，而不是人工）。我必须使用ObjectOutputStream还是有更好的方法？目的是使用尽可能少的字节。谢谢马丁 参考方案 Java序列化（ObjectOutputStream / ObjectInputStream）是将对象序列化为八位字节序列的一种通用方法。但…