算法找到的第n个数量最多规模为n的两个数组 [英] An algorithm to find the nth largest number in two arrays of size n

问题描述

我有这样一个问题：

由于两个排序列表（存储在阵列）大小为n的，找一个O（log n）的   算法，计算在该工会的第n个最大元素   两份清单。

Given two sorted lists (stored in arrays) of size n, find an O(log n) algorithm that computes the nth largest element in the union of the two lists.

我可以看到有可能在这里一招，因为它需要第n个最大元素和数组的大小为n的还可以，但我无法弄清楚它是什么。我在想，我能适应计数排序，将这项工作？

I can see there is probably a trick here as it requires the nth largest element and the arrays are also of size n, but I can't figure out what it is. I was thinking that I could adapt counting sort, would that work?

推荐答案

比较A [N / 2]和B [N / 2]。如果相等，任何人是我们的结果。这个算法其它停止条件是，当两个数组的大小为1（无论是最初还是经过多次递归步）的。在这种情况下，我们只是选择了最大的A [N / 2]和B [N / 2]。

Compare A[n/2] and B[n/2]. If equal, any of them is our result. Other stopping condition for this algorithm is when both arrays are of size 1 (either initially or after several recursion steps). In this case we just choose the largest of A[n/2] and B[n/2].

如果A [N / 2]其中， B〔N / 2]，递归重复此过程的[]下半年和B上半年[]。

If A[n/2] < B[n/2], repeat this procedure recursively for second half of A[] and first half of B[].

如果A [N / 2]> B〔N / 2]，递归重复此过程的B〔]下半年的[]上半场。

If A[n/2] > B[n/2], repeat this procedure recursively for second half of B[] and first half of A[].

由于每一步的问题规模（在最坏的情况下）减半，我们会为O（log n）的算法。

Since on each step the problem size is (in worst case) halved, we'll get O(log n) algorithm.

总是除以数组大小由两个拿到指标正常工作仅当 N 是二的幂。选择指标更正确的方式（对任意 N ）将使用相同​​的策略，一个阵列但选择互补指数： J = NI 其他的。

Always dividing array size by two to get the index works properly only if n is a power of two. More correct way of choosing indexes (for arbitrary n) would be using the same strategy for one array but choosing complementing index: j=n-i for other one.

这篇关于算法找到的第n个数量最多规模为n的两个数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！