0

例如数组:{1, 5, 2, 3, 2, 10}

范围:0-1 答案:5 范围:2-4 答案:3 范围:0-5 答案:10 等等。

4

4 回答 4

11

如果数组未排序,则无法执行您要求的操作。

要找到最大值,您至少需要检查范围内的所有元素,这需要 O( n )。

如果您允许对数据进行某种形式的预处理,这很容易。您可以只用答案构建一个 n 2查找表。然后你可以在恒定时间内找到任何范围的最大值。

于 2012-02-27T15:07:29.527 回答
4

这是不可能的。您必须访问每个元素。

如果您的数组是先验排序的,那么它是 O(1) 操作。

于 2012-02-27T15:07:33.570 回答
1

另请参阅: 从数字数组中获取最小值或最大值的最佳方法是什么?

正如其他人指出的那样,这是不可能的

于 2012-02-27T15:12:27.423 回答
0

@Daniel Talamas 如果我理解正确,你想要这个:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int maxlement(int range1,int range2) {
std::vector<int> v{ 1, 5, 2, 3, 2, 10 };
std::vector<int>::iterator result;

result = std::max_element(v.begin()+range1, v.begin()+range2+1);
int dist = std::distance(v.begin(), result);
return v[dist];

}
int main() {
int range1,range2;
cout<<"From ";
cin>>range1;
cout<<"To ";
cin>>range2;
cout<<"Max Element Is "<<maxlement(range1,range2);
return 0;
}
于 2012-02-27T15:23:21.950 回答