有一个数字数组，这个数组是不规则的，我们应该找到一个最大数（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 。
这很好，或者它可能会限制时间？有人有其他想法吗？
谢谢
其中c++有一个函数被调用std::nth_element，它可以在线性时间内找到数组的第 n 个元素。使用此函数，您应该找到第N - n- 个元素（其中N是数组中元素的总数）并从中减去 1。
当您寻求解决方案时，C您无法使用此功能，但您可以类似地实施您的解决方案。nth_element执行与 qsort 非常相似的操作，但它仅对数组中第 n 个元素所在的部分执行分区。
现在让我们假设你已经nth_element实现了。我们将执行类似二分搜索和nth_element. 首先我们假设问题的答案是数组的中间元素（即第 N/2 个元素）。我们使用nth_element并找到第N/2th 个元素。如果它比N/2我们知道的更多，那么您的问题的答案至少是N/2，否则它会更少。无论哪种方式，为了找到答案，我们只会继续使用N/2第 th 个元素创建的两个分区之一。如果这个分区是正确的（大于 的元素N/2），我们继续解决相同的问题，否则我们开始搜索第一个元素M左侧的最大元素，该N/2元素至少具有x更大的元素，使得x + N/2 > M. 这两个子问题将具有相同的复杂性。您继续执行此操作，直到您感兴趣的间隔为 length 1。
现在让我们证明上述算法的复杂度是线性的。第一个nth_element是按 的顺序线性执行操作N，第二个nth_element是只考虑数组的一半将按N/2第三个顺序执行操作 -N/4依此类推。总而言之，您将按N + N/2 + N/4 + ... + 1. 这个总和小于2 * N因此您的复杂性仍然是线性的。
您的解决方案比我上面建议的要慢，因为它具有复杂性O(n*log(n))，而我的解决方案具有O(n).
我将使用使用枢轴值的排序算法的修改变体。
原因是您希望对尽可能少的元素进行排序。
所以我会使用qsort作为我的基本算法，让枢轴元素控制要排序的分区（你只需要排序一个）。