5

我最近在某个地方遇到了一个非常好的面试问题，我想问你们所有的天才，什么是最优化的解决方案。所以问题如下：给定一个整数数组，找到一个最大数n，使得至少有n个数组元素大于n。输入数组未排序。

例如：

输入：1,2,5,7,8,10 输出：n = 4

输入：0,2,7,8,19,5,45,9,23 输出：n = 6

我能想到的一种解决方案（如果数组是排序的情况）是顺序扫描数组中的所有元素以找出 min:n 和 max:n。然后在 min:n 到 max:n 之间递增整数并一一检查。但这是 O(N) 解决方案。有人可以推荐一个更好的吗？
例如：对于输入 1 min:n = 2 和 max:n = 5
那么您将检查数字 2,3 和 4 作为答案。

从答案来看，如果数组未排序，则没有比 O(N) 更好的解决方案。但是下一个问题是如果给定的数组是排序的呢？

pseudocode :
// this assumes sorted input.
pubic int findhighestIndex(List<Integer> input){
it min=0,max=0,n=0,maxIndex=0;
for(int i=0;i<input.size();i++){
    if( input.get(i)>(input.size()-i) ){
        max=input.get(i);
        maxIndex=i;
        min=input.get(i-1);
        break;
    }
    else if(input.get(i)<(input.size()-i)){
        max=min=input.get(i);
    }
}
int i=max;
while( i>=min && (input.size()-maxIndex)<i ){
i--;
}
System.out.println(i);
}


更新：这个问题也称为查找 h-index

4

6 回答 6

9

编辑：刚刚想出了O(n)未分类案例的解决方案:)见下文！

排序：

这可以在O(log N) 中通过对 的二进制搜索来解决n。我将在这里使用 OP 的符号，我们正在寻找的答案在哪里N = # of elements并且是。n

如果数组已排序，则基本上意味着我们需要找到一个位置[N - n]，以便数组中的该位置包含一个大于n- 如果是这样，那么无论重复值如何，至少有n大于它的值。

请注意，答案总是可能的，因为在最坏的情况下答案是0，并且总是至少有0 个元素大于它。显然，对于较低的值，答案总是“更容易”，因为它更容易找到大于 1 的 1 个元素，而不是大于 10 的 10 个元素。但更重要的是，这个函数遵循单调（非递减）行为，这允许我们对其使用二进制搜索。

思路如下：

int N = 9;
int arr[10] = {0,2,5,7,8,9,19,23,45};

int lo = 0, hi = N+1, mid;
while(hi-lo > 1){
    mid = (hi+lo)/2;
    if(arr[N-mid] > mid) lo = mid;
    else hi = mid;
}
n = lo; //highest value that worked

细分：数组的大小9。二进制搜索可能会开始尝试 value n = 5，因此我们只需检查数组末尾的第 5 个元素是否大于 5。在这种情况下，8 > 5我们可以尝试更好的答案。然后搜索会尝试7，但位置的元素[N-7]是5，它小于 7 并且不满足我们的约束。因此，搜索的最后一次尝试是 value 6，它返回 true as 7 > 6。

未分类：

对于未排序的情况，这个想法非常相似！我们可以O(n)通过使用选择算法来识别第 [Nn] 个元素，并在每一步以与二分搜索相同的方式划分搜索空间来解决它。

我们从从[0]to开始搜索[N-1]以找到中间(N/2 th)元素，我们可以在另一个O(N)步骤中重新排列数组，使中间元素放置在正确的位置，并且它之前的每个元素都有一个 value <= median，而它之后的每个元素都有一个 value >=median.

现在，如果该值大于n（在这种情况下N/2），我们在上面显示了至少有大于的n元素n，因此我们只需要在数组的下半部分进一步搜索。（如果中值低于n，我们只考虑数组的大半部分）

现在，假设median >= N/2我们将从 index[0]到重复相同的过程，在[N/2]中使用选择“排序” O(N/2)，依此类推，每次将搜索空间除以 2。

C++代码如下：

int N = 9;
int arr[9] = {0,2,7,8,19,5,45,9,23};

int lo = 0, hi = N, mid;
while(hi-lo > 1){
  mid = (hi+lo)/2;
  std::nth_element(arr+lo, arr+mid, arr+hi);
  if(arr[mid] > N-mid) hi = mid;
  else lo = mid;
}
n = N-hi;

最后，我们实现了一个复杂度O(N) + O(N/2) + O(N/4) + ... = O(2*N) = O(N)

于 2013-07-02T04:45:05.890 回答
4

不涉及魔法

如果您一直在阅读上面的内容并想“我怎么会在面试中提出这个问题”或“我真的可以相信这段代码没有错误”，那就不要再看了！让我向您介绍“正式程序设计”的快乐世界！

在这个答案中，我将解释我们如何将问题陈述转化为一对不等式，这反过来会迫使我们进行二分搜索，所以只有一种写法。我还将捕获先前答案中遗漏的几个错误和极端案例。

全部设置好

假设我们有一个排序的、非空的 size 数组N=7。

N: 7
    i: 0 1 2 3 4 5 6
ar[i]: 3 3 4 5 6 6 7

我们真正想要的是i一个

ar[i] <= N-i-1

但是，我们想要最大的那个，也就是最右边的那个，所以它一定是

ar[i+1] > N-i-1

变得正式

我们要做的是保留两个变量lo和hist。我们总是有

ar[lo] <= N-lo-1   (1)
ar[hi] > N-hi-1    (2)

（注意在第二个等式中替换为i+1for ）。hi

然后，我们将小心地将变量移向彼此，直到lo+1 = hi找到i我们最初寻找的变量。

现在我们需要一些起始值。

  • 一个选择hi可能是N。这超出了数组的范围，但我们永远不会读取它，所以我们假设它是一个满足等式 (2) 的巨大值。

  • 更难lo，因为我们甚至可以确定这样的值存在吗？不！该数组[7,8,9]没有满足所需属性的索引，因此我们找到了第一个极端情况。我们可以假设，如果任何索引满足 (1) 它一定是0，但是我们必须引入一个测试来查看它是否真的可以继续进行。

甜的！我们避免了一个讨厌的错误。

将其插入代码

好的，此时是调用二分搜索的时候了。真的工作已经完成了，我们简单地写：

if ar[0] > N-0-1:
    panic("No solutions found!")

lo, hi = 0, N
while lo+1 != hi:
    mid = (lo + hi)/2
    if ar[mid] <= N-mid-1:
        lo = mid
    if ar[mid] > N-mid-1:
        hi = mid

print "The solution is ar[%d] = %d" % (lo, ar[lo])

（请注意，我们可以将第二个更改if为 an else，因为条件彼此相反）

结果

在原始示例上运行它会给我们：

The solution is ar[2] = 4

为了好玩，我还尝试使用相同的数组运行“i Code 4 Food”的代码。我认为他认为价值观是独一无二的，因为他回来了

lo = 4

这显然不起作用，因为ar[4] = 6, 之后只有两个值。

于 2013-09-19T11:05:21.590 回答
2

不需要排序。

如果 a[1...N] 是输入数组，请注意您正在寻找的答案是 <= N。

因此，对于 0 <= i <= N 中的每个数字 i，我们尝试跟踪元素的数量 > i。

为了在 O(N) 时间内计算它，我们分配了一个大小为 N+1 的数组 S，初始化为零。

通过 a，当你遇到一个元素 a (= a[j])，如果 a > N，你增加 S[N+1]，否则你增加 S[a]。

元素数 > i 将由 S[i+1] + S[i+2] + ... + S[N+1] 给出。

我们可以通过 S 从 N+1 到 1 来计算每个 i 的值，并保持一个累积和。

于 2013-07-02T14:07:51.173 回答
0

“i Code 4 Food”给出的答案绝对是绝妙的。

但我认为你可以用另一种方式决定起点（我不知道这是否更好）。

假设满足给定条件的元素是n。现在假设我想从排序数组中随机选择一个元素（让整数的随机变量为X）然后P( X > n) >= n/N （其中 N 是数组中元素的总数）。

但是从马尔可夫不等式我们有P( X > n) <= E[X]/n。这里 E[X] 是期望值，即在这种情况下的平均值。

考虑到上述两个不等式，我们有n/N <= E[X]/n即n^2 <= Sum

考虑例如输入：1,2,5,7,8,10，我们将从不等式n^2 <= 33所以n < 6得到。所以我们可以在这里设定我们的起点。

于 2013-07-02T06:34:27.390 回答
0

如果您不允许排序，这只是另一种解决方案。

O(N log M)

在哪里：

N=输入中的元素数

M=输入中的数字范围

算法：

对答案进行二分搜索。

 First find max element(M) of input using linear scan.
 int lo=0, hi=M
 while(hi-lo>1)
 {
  int mid=(lo+hi)/2;
  int t=0;
  for(int i=0;i<N;i++)if(A[i]>mid)t++;
  if(t>=mid)lo=mid;
  else hi=mid-1;
 }
 return lo;

如果您在整数范围内进行操作，则log M因子仅为32。

于 2013-07-02T06:52:33.130 回答
-1

由于我对威廉·盖茨的回答的编辑因“推广产品或服务”（什么？）而被拒绝，所以我在这里复制了实现他的解决方案的代码。在 C++ 中，这可以在保证线性时间内对任何数据集实现，如下所示：

#include <algorithm>
#include <vector>

size_t solve(std::vector<int> const &input) {
    std::vector<size_t> counts(input.size() + 1, 0);
    for (auto val : input) {
        if (0 <= val)
            ++counts[std::min(static_cast<size_t>(val), input.size())];
    }
    size_t n{ input.size() };
    for (size_t numGreater{ counts[n] }; 0 < n
         && numGreater < n; numGreater += counts[--n]);
    return n;
}

请注意，这需要 O(N) 额外内存和 O(N) 时间。

于 2019-03-01T01:34:23.603 回答