c - 找到数组中的最大数

Question

有一个数字数组，这个数组是不规则的，我们应该找到一个最大的数字(n)，至少有n个数字比它大(这个数字可能在数组中，也可能不在数组中)

例如，如果我们给出 2 5 7 6 9 数字 4 是最大数字，则至少有 4 个数字(或更多)大于 4(5 6 7 9 更大)

我解决了这个问题，但我认为它给出了大量数字的时间限制，所以我想用另一种方式解决这个问题所以我使用合并排序进行排序，因为它需要 nlog(n) 然后我使用一个计数器，它从 1 计数到 k 如果我们有 k 个数大于 k 我们再次计数例如我们计数从 1 到 4 然后在 5 中我们没有 5 个数字大于 5 所以我们给 k-1 = 4 这就是我们的 n 。

这很好还是可能会限制时间？有人有其他想法吗？

谢谢

Answer 1

c++ 中有一个名为std::nth_element 的函数，它可以在线性时间内找到数组的第n 个元素。使用此函数，您应该找到第 N - n 元素(其中 N 是数组中元素的总数)并从中减去 1。

当您在 C 中寻求解决方案时，您不能使用此函数，但您可以类似地实现您的解决方案。 nth_element 执行的操作与 qsort 非常相似，但它只对数组中第 n 个元素所在的部分进行分区。

现在假设您已经实现了 nth_element。我们将执行类似于二进制搜索和 nth_element 的组合。首先我们假设问题的答案是数组的中间元素(即第 N/2 个元素)。我们使用 nth_element 并找到第 N/2 个元素。如果它大于 N/2，我们知道你的问题的答案至少是 N/2，否则它会更少。无论哪种方式，为了找到答案，我们将只继续由第 N/2 元素创建的两个分区之一。如果这个分区是正确的(大于 N/2 的元素)我们继续解决同样的问题，否则我们开始搜索左边的最大元素 M N/2 至少有 x 个更大元素的元素，例如 x + N/2 > M。这两个子问题将具有相同的复杂性。您继续执行此操作，直到您感兴趣的间隔长度为 1。

现在我们来证明上述算法的复杂度是线性的。第一个 nth_element 是线性的，按照 N 的顺序执行操作，第二个 nth_element 只考虑数组的一半，将按顺序执行操作N/2 第三个 - 按照 N/4 的顺序，依此类推。总之，您将按照 N + N/2 + N/4 + ... + 1 的顺序执行操作。此总和小于 2 * N 因此您的复杂度仍然是线性的。

您的解决方案比我上面提出的方案渐近慢，因为它的复杂度为 O(n*log(n))，而我的解决方案的复杂度为 O(n).