0
A
答えて
11
配列がソートされていない場合は、あなたが求めていることをする方法がありません。 にあなたは少なくとも必要最大値を見つけるには
はO(nはを)取る範囲ですべての要素を点検します。
データの前処理を許可すると簡単です。あなたは答えを使ってn ルックアップテーブルを構築することができます。次に、一定の時間内に任意の範囲の最大値を見つけることができます。
4
これは不可能です。すべての要素を訪問する必要があります。
あなたの配列が先験的にソートされている場合は、O(1)操作です。
1
もここを参照してください: What is the best way to get the minimum or maximum value from an Array of numbers?
他の人が指摘したように、それは不可能だ
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;
}
+1
線形ではなく対数でのみ、時間。 –
関連する問題
- 1. O(n log n)時間内に特別な点kを見つけるアルゴリズム
- 2. 日付範囲の最大値と最大値を見つける(ユーザ選択)
- 3. パンダは時間のローリングウィンドウで最大値を見つける
- 4. 値の間の数値の範囲を見つける
- 5. マインドストームEV3 - アレイ内で最大の数を見つける
- 6. Pythonリストのインデックスが範囲外です - ローカル最大値を見つける
- 7. チャペルでアレイの最大値を見つける方法
- 8. 範囲内の最大値を見つけて他のセルの値に1を加算するVBAコード
- 9. から取得できる最大値を見つけるN
- 10. 任意の所定の間隔でアレイ内の5つの最大値を見つける効率的方法
- 11. 時間範囲でオーバーラップを見つける
- 12. O(n)時間内に配列内に10個の最大整数を見つける
- 13. #VALUEの名前付き範囲の最大値を見つけよう! - エラー
- 14. 数値の範囲内のギャップを見つける
- 15. データベーステーブルの範囲内の値を見つける
- 16. 範囲キーの最高値を見つける
- 17. 測定アレイの周波数の最小値と最大値を見つける
- 18. 範囲内の最高12個の連続値を見つける
- 19. 範囲内のSQLチェック時間値
- 20. 範囲+ループ内の値を見つける
- 21. 可視範囲内のセル値を見つける方法
- 22. pythonで制限時間内に最大のフィボナッチ数を見つける
- 23. ファイル内の最小値/最大値を見つける方法
- 24. 最小範囲と最大範囲のテーブル内の値の場所の検索
- 25. セルの範囲から最大の2進数を見つける
- 26. 2つの数値の間の範囲でポイントを見つける
- 27. 範囲内の最大値を持つセルからのセルオフセットの戻り値
- 28. 大きい範囲のすべてのサブ範囲を見つける
- 29. VBA - 範囲2の最大値からの範囲の設定
- 30. Excel VBA対応範囲の最小値から最大値に基づいて範囲内のセルアドレスを検索
を。並べ替えられていないシーケンスで最大値を見つけるには、各値を少なくとも1回は調べなければなりません。これはアルゴリズムO(n)を作る。 – sbi
@sbi:配列を前処理して、検索ツリー/テーブル/を構築しないと、サブレンジを検索するよりもすばやく最大のサブレンジを得ることができます。おそらく、それは質問が何を求めているかですが、それはちょっと狭いです。 –
@Mike:それは本当ですが、私はそのような野獣を「並べ替えられていない配列」と呼んでいません。私はこの抜け穴を故意に残しました、あなたは知っていますか? ':)' – sbi