私はこの質問にウェブサイトで出くわしました。そこで述べたように、アマゾンのインタビューで聞かれました。与えられた制約で適切な解決策を見つけることができませんでした。
与えられた整数の配列から、 とO(n)時間で3 つの要素をn見つけます。a[i] < a[j] < a[k]i < j < k
質問する
21005 次
14 に答える
33
だからここにあなたが問題を解決する方法があります。配列を 3 回反復処理する必要があります。最初の反復では、それらよりも大きい要素を持つすべての値を右側にマークし、2 番目の反復では、それらよりも小さいすべての要素を左側にマークします。あなたの答えは、両方を持つ要素を使用することになります。
int greater_on_right[SIZE];
int smaller_on_left[SIZE];
memset(greater_on_rigth, -1, sizeof(greater_on_right));
memset(smaller_on_left, -1, sizeof(greater_on_right));
int n; // number of elements;
int a[n]; // actual elements;
int greatest_value_so_far = a[n- 1];
int greatest_index = n- 1;
for (int i = n -2; i >= 0; --i) {
if (greatest_value_so_far > a[i]) {
greater_on_right[i] = greatest_index;
} else {
greatest_value_so_far = a[i];
greatest_index = i;
}
}
// Do the same on the left with smaller values
for (int i =0;i<n;++i) {
if (greater_on_right[i] != -1 && smaller_on_left[i] != -1) {
cout << "Indices:" << smaller_on_left[i] << ", " << i << ", " << greater_on_right[i] << endl;
}
}
このソリューションは、配列全体で 3 回繰り返されるため、線形です。解決策全体を提供していないので、左側で自分を訓練して、私の考えを理解できるかどうかを確認してください。いくつかのヒントを提供できなくて申し訳ありませんが、実際の解決策を示さずにヒントを提供する方法を理解できませんでした。
これで問題が解決することを願っています。
于 2012-04-04T09:40:00.350 に答える
3
O(1) 余分なスペース (4 つの変数) を持つワンパス線形時間。非常に効率的です (反復ごとに数回の比較/分岐のみであり、データのシャッフルはあまりありません)。
これは私のオリジナルのアイデアやアルゴリズムではありません。アイデアフォークでコードを整理してコメントしただけです。そこにあるコードに新しいテストケースを追加して、オンラインで実行できます。オリジナルは Kenneth によるもので、 www.geeksforgeeks.org のスレッドのコメントに投稿されています。素晴らしいアルゴリズムですが、元の実装には、実際のループの外側に非常にばかげたコードがいくつかありました。（たとえば、ローカル変数の代わりに、クラスで2つのメンバー変数を使用し、関数をメンバー関数として実装しましょclass Solutionう...そして、変数名は最悪です。私はかなり冗長なものを選びました。）
ケネス、コードを回答として投稿したい場合は、どうぞ。アルゴリズムのクレジットを盗もうとしているわけではありません。（ただし、この説明を書き、なぜそれが機能するのかを考えてみました。）
ディスカッション スレッドの上の主な記事には、Ivaylo Strandjev の回答と同じ解決策があります。(メイン記事のコードは、Pramod がこの質問への回答として投稿したもので、Ivalyo の回答の数か月後に投稿されました。それが、そこのコメントで興味深い回答を見つけた方法です。)
解決策のすべてではなく、解決策を見つけるだけでよいため、予期したほど多くの特殊なケースはありません。状態として保持する適切なものを選択すれば、見た可能性のあるすべての開始値と中間値を追跡する必要はなく、まったくバックトラックする必要もないことがわかります。
主なトリックは次のとおりです。
単調に減少する一連の値の最後の値だけを考慮する必要があります。これは、1 番目 (低) と 2 番目 (中) の候補要素の両方に適用されます。
中間要素の小さい候補を見つけたら、そこから新たに開始して、最終要素またはさらに優れた中間候補を探すだけです。
現在の中間候補よりも小さい要素の前に 3 つの増加する要素のシーケンスをまだ見つけていない場合、min-so-far と新しい小さい中間候補は、可能な限り (寛容で、柔軟に) 適切です。あなたがすでにチェックした数のうち。(これを表現するためのおそらくより良い方法については、コード内のコメントを参照してください。)
他のいくつかの回答は、中間ではなく、新しい最小または最大の要素が表示されるたびに、最初からやり直すという間違いを犯しています。見た現在の最小値を追跡しますが、新しい中間値が表示されるまで反応したり利用したりしません。
新しい中間要素の候補を見つけるには、それらが現在の中間候補よりも小さいかどうかを確認し、これまでに見た最小要素を != します。
このアイデアを 4 つ以上の値に連続して拡張できるかどうかはわかりません。新しい候補の 3 番目の値を見つけるには、全体の最小値とは別に、現在の候補の 2 番目と 3 番目の間の最小値を追跡する必要がある場合があります。これはトリッキーになり、さらに多くの条件が必要になる可能性があります。しかし、一定サイズの状態とバックトラックなしの 1 つのパスで正しく実行できる場合でも、線形時間になります。
// Original had this great algorithm, but a clumsy and weird implementation (esp. the code outside the loop itself)
#include <iostream>
#include <vector>
using namespace std;
//Find a sorted subsequence of size 3 in one pass, linear time
//returns an empty list on not-found
vector<int> find3IncreasingNumbers(int * arr, int n)
{
int min_so_far = arr[0];
int c_low, c_mid; // candidates
bool have_candidates = false;
for(int i = 1; i < n; ++i) {
if(arr[i] <= min_so_far) // less-or-equal prevents values == min from ending up as mid candidates, without a separate else if()continue;
min_so_far = arr[i];
else if(!have_candidates || arr[i] <= c_mid) {
// If any sequence exists with a middle-numbers we've already seen (and that we haven't already finished)
// then one exists involving these candidates
c_low = min_so_far;
c_mid = arr[i];
have_candidates = true;
} else {
// have candidates and arr[i] > c_mid
return vector<int> ( { c_low, c_mid, arr[i] } );
}
}
return vector<int>(); // not-found
}
int main()
{
int array_num = 1;
// The code in this macro was in the original I forked. I just put it in a macro. Starting from scratch, I might make it a function.
#define TRYFIND(...) do { \
int arr[] = __VA_ARGS__ ; \
vector<int> resultTriple = find3IncreasingNumbers(arr, sizeof(arr)/sizeof(arr[0])); \
if(resultTriple.size()) \
cout<<"Result of arr" << array_num << ": " <<resultTriple[0]<<" "<<resultTriple[1]<<" "<<resultTriple[2]<<endl; \
else \
cout << "Did not find increasing triple in arr" << array_num << "." <<endl; \
array_num++; \
}while(0)
TRYFIND( {12, 11, 10, 5, 6, 2, 30} );
TRYFIND( {1, 2, 3, 4} );
TRYFIND( {4, 3, 1, 2} );
TRYFIND( {12, 1, 11, 10, 5, 4, 3} );
TRYFIND( {12, 1, 11, 10, 5, 4, 7} );
TRYFIND( {12, 11, 10, 5, 2, 4, 1, 3} );
TRYFIND( {12, 11, 10, 5, 2, 4, 1, 6} );
TRYFIND( {5,13,6,10,3,7,2} );
TRYFIND( {1, 5, 1, 5, 2, 2, 5} );
TRYFIND( {1, 5, 1, 5, 2, 1, 5} );
TRYFIND( {2, 3, 1, 4} );
TRYFIND( {3, 1, 2, 4} );
TRYFIND( {2, 4} );
return 0;
}
イニシャライザ リストをパラメータとして使用できる CPP マクロを作成するのは見苦しいです:
中括弧で囲まれたイニシャライザをマクロ パラメータとして渡すことは可能ですか?
ただし、 4 か所を編集arr4することなく、新しいテスト ケースを簡単に追加できることは非常に価値がありました。arr5
于 2015-11-29T11:43:34.757 に答える
1
ここに解決する別のアプローチを投稿しました。
#include<stdio.h>
// A function to fund a sorted subsequence of size 3
void find3Numbers(int arr[], int n)
{
int max = n-1; //Index of maximum element from right side
int min = 0; //Index of minimum element from left side
int i;
// Create an array that will store index of a smaller
// element on left side. If there is no smaller element
// on left side, then smaller[i] will be -1.
int *smaller = new int[n];
smaller[0] = -1; // first entry will always be -1
for (i = 1; i < n; i++)
{
if (arr[i] < arr[min])
{
min = i;
smaller[i] = -1;
}
else
smaller[i] = min;
}
// Create another array that will store index of a
// greater element on right side. If there is no greater
// element on right side, then greater[i] will be -1.
int *greater = new int[n];
greater[n-1] = -1; // last entry will always be -1
for (i = n-2; i >= 0; i--)
{
if (arr[i] > arr[max])
{
max = i;
greater[i] = -1;
}
else
greater[i] = max;
}
// Now find a number which has both a greater number on
// right side and smaller number on left side
for (i = 0; i < n; i++)
{
if (smaller[i] != -1 && greater[i] != -1)
{
printf("%d %d %d", arr[smaller[i]],
arr[i], arr[greater[i]]);
return;
}
}
// If we reach number, then there are no such 3 numbers
printf("No such triplet found");
return;
}
// Driver program to test above function
int main()
{
int arr[] = {12, 11, 10, 5, 6, 2, 30};
int n = sizeof(arr)/sizeof(arr[0]);
find3Numbers(arr, n);
return 0;
}
于 2012-06-08T20:35:02.883 に答える
0
私のアプローチ - O(N) 回 2 パス O(1) 2 つの変数を使用した空間
アクセスする配列の各要素について、この要素が中央の要素であるかどうかをチェックするためにその左に可能な最小値を維持し、この要素が候補の 3 番目の要素であるかどうかをチェックするためにその左に最小の中央要素の記録を保持しますまたは、これまでに見つかった値よりも低い値を持つ中間要素を形成する可能性があります。min so far と middle so far を INT_MAX に初期化します。
したがって、各要素を確認する必要があります。
特定の配列要素が中間要素の最小値よりも大きい場合、この配列要素よりも thi を 3 番目の要素とし、最小の中間要素を中間要素として答えます (後で 3 番目の要素を 1 ずつ検索する必要があります)。合格）
それ以外の場合、特定の配列要素が最小値よりも大きい場合、この要素は中間要素の候補になる可能性があり、中間要素の候補が現在の中間要素よりも小さいかどうかを確認する必要がある場合は、現在の中間要素を更新します
ELSE 特定の配列要素がこれまでの最小値よりも小さい場合、 arr[i] でこれまでの最小値を更新します。
したがって、このようにして、アクセスする配列の各要素について、その要素が中央の要素であるかどうかをチェックするためにその左側に可能な最小値を維持し、この要素が候補の 3 番目の要素、またはこれまでに見つかった値よりも低い値を持つ中間要素を形成する可能性があります。
#名前空間 std を使用してインクルードします。
int main()
{
int i,j,k,n;
cin >> n;
int arr[n];
for(i = 0;i < n;++i)
cin >> arr[i];
int m = INT_MAX,sm = INT_MAX,smi;// m => minimum so far found to left
for(i = 0;i < n;++i)// sm => smallest middle element found so far to left
{
if(arr[i]>sm){break;}// This is the answer
else if(arr[i] < m ){m = arr[i];}
else if(arr[i] > m){if(arr[i]<sm){sm = arr[i];smi = i;}}
else {;}
}
if((i < n)&&(arr[i]>sm))
{
for(j = 0;j < smi;++j){if(arr[j] < sm){cout << arr[j] << " ";break;}}
cout << sm << " " << arr[i]<< endl;
}
else
cout << "Such Pairs Do Not Exist" << endl;
return 0;
}
于 2017-01-07T09:23:19.300 に答える
-1
max-heap O（n）を作成してから、Extract-Max O（1）を3回実行するとどうなりますか？
于 2012-04-10T20:59:46.033 に答える
-1
申し訳ありませんが、パズルを解くしかありませんでした... これが私の解決策です。
//array indices
int i, j, k = -1;
//values at those indices
int iv, jv, kv = 0;
for(int l=0; l<a.length(); l++){
//if there is a value greater than the biggest value
//shift all values from k to i
if(a[l]>kv || j == -1 || i == -1){
i = j;
iv = jv;
j = k;
jv = kv
kv = a[l]
k = l
}
if(iv < jv && jv < kv && i < j && j < k){
break;
}
}
于 2012-04-04T09:16:59.237 に答える
-1
2 つの変数を作成してみてください。
1. index_sequence_length_1 = index i such
a[i] is minimal number
2. index_sequence_length_2 = index j such
There is index i < j such that a[i] < a[j] and a[j] is minimal
配列全体を反復し、各反復でこの変数を更新します。
[index_sequence_length_2] より大きい要素を反復処理すると、シーケンスが見つかりません。
于 2012-04-04T09:18:56.050 に答える
-1
これは、反復が 1 回だけのソリューションです。
スタックを使用して、インデックス k ごとに、a[i] < a[j] < a[k] のような 2 つの他のインデックス i & j が存在するかどうかを計算しています。
bool f(vector<int> a) {
int n = a.size();
stack<int> s;
for (int i = 0; i < n; ++i)
{
while(!s.empty() and a[s.top()]>=a[i]){
s.pop();
}
if (s.size()>=2) // s.size()>=k-1
{
return 1;
}
s.push(i);
}
return 0;
}
そして重要なことは、この問題を k 個のインデックスではなく、一般的なケースで M 個のそのようなインデックスに拡張できることです。
于 2015-11-26T18:55:01.443 に答える
-1
1回繰り返して完了：
public static int[] orderedHash(int[] A){
int low=0, mid=1, high=2;
for(int i=3; i<A.length; i++){
if(A[high]>A[mid] && A[mid]>A[low])
break;
if(A[low]>A[i])
low=mid=high=i;
else if(low == mid && mid == high)
mid = high = i;
else if(mid == high){
if(A[high]<A[i])
high = i;
else
mid = high = i;
}
else if(A[mid]<A[i])
high = i;
else if( A[high]<A[i]){
mid = high;
high =i;
}
else
mid=high=i;
}
return new int[]{A[low],A[mid],A[high]};
}//
次に、メインでテストします。
public static void main(String[] args) {
int[][] D = {{1, 5, 5, 3, 2, 10},
{1, 5, 5, 6, 2, 10},
{1, 10, 5, 3, 2, 6, 12},
{1, 10, 5, 6, 8, 12, 1},
{1, 10, 5, 12, 1, 2, 3, 40},
{10, 10, 10, 3, 4, 5, 7, 9}};
for (int[] E : D) {
System.out.format("%s GIVES %s%n", Arrays.toString(E), Arrays.toString(orderedHash(E)));
}
}
于 2012-04-04T19:16:37.880 に答える