並べ替えられたサイズ4の配列を線形時間で配列内で見つける

Question

数字の配列が与えられており、サイズの小さい部分配列を見つけ出し、昇順にソートします。

for eg ARRAY    : -4 2 8 3 1 5 
sorted subsequence of size 4 : -4 2 3 5 

PS：サイズ3（see this）のソートされたサブシーケンスを見つける方法があります。私は同じ行に沿って考えようとしていますが、4つの整数の解を見つけることはできません。

Answer 1

kを入力に渡すことで、固定サイズのソート済みサブシーケンスが見つかる解決策を次に示します。k+1各パスは左から右に行われます。

パス1：補助配列p1[0..n-1]を作成します。 p1[i]はarr[i]より小さい数字のjを格納し、arr[i]の左側にあります（つまり、j<iとarr[j]<arr[i]）。 p1[i]には、そのような要素がない場合は-1を含める必要があります。 （p1は、サイズ3の解決策のsmallerアレイと同じです）。

2を渡す：補助配列p2[0..n-1]を作成します。 p2[i]は、arr[i]より小さい数字のjを格納し、arr[i]の左側にあり、p1[j] != -1（換言すれば、j<i,arr[j]<arr[i]、およびp1[j]!=-1）の数字を格納する必要があります。そのような要素がない場合は、p2[i]は-1を含む必要があります。

....

パスK：補助アレイpk[0..n-1]を作成します。 pk[i]arr[i]よりも小さい番号のインデックスjを格納する必要があり、arr[i]の左側にあり、その結果p(k-1)[j] != -1（言い換えれば：j<i、arr[j]<arr[i]、及びp(k-1)[j]!=-1）。 pk[i]には、そのような要素がない場合は-1を含める必要があります。

k通過後、各要素は、k+1のソートされたサブシーケンスの中で最大の要素に対応します（pk[i] != -1）。

k番目のパスのための擬似コード（K> 1）：

function do_kth_pass(pk[], p_k_minus_1[]) 
    min = -1 
    for i in 0..n-1: 
     if min != -1 and arr[i] > arr[min]: 
      pk[i] = min 
     else 
      pk[i] = -1 
     if p_k_minus_1[i] != -1 and (min == -1 or arr[i] < arr[min]): 
      min = i 

例：3回のパス後

Index: 0 1 2 3 4 5 
Array: -4 2 8 3 1 5 
p1:  -1 0 0 0 0 0 
p2:  -1 -1 1 1 -1 4 
p3:  -1 -1 -1 -1 -1 3 

、あなたはP3 [5]を有する= -1、そうソートサブ！サイズ4のものが存在する。その要素のインデックスは、次のとおり0,1,3,5

Answer 2

同様これに加えて、サイズ3のサブシーケンスのために行われたものに関して、またbetweenSmallerAndCurrent配列を有する、smallerとgreater配列を作成しているp1[p2[p3[5]]], p2[p3[5]], p3[5], 5これは、最も小さい要素と現在の要素の間の値のインデックスを格納します（値とインデックスの両方）。より明示的に：

betweenSmallerAndCurrent[i] = -1 or 

input[smaller[i]] < input[betweenSmallerAndCurrent[i]] < input[value[i]] and 
smaller[i] < betweenSmallerAndCurrent[i] < value[i] 

これを構成することは非常に簡単です。

ibetweenSmallerAndCurrent[i]smaller[betweenSmallerAndCurrent[i]]greater[i]のすべてが初期化されています。 smaller[i]には[2,3,1,4,5]のようなものがあります。この場合、4になると、次に小さい値の3が現在の最小値の1の前になります。

例：

Indices: 0 1 2 3 4 5 6 7 
Input: 12 11 10 5 6 2 9 30 

smaller: -1 -1 -1 -1 3 -1 5 5 
betweenSmallerAndCurrent: 
     -1 -1 -1 -1 -1 -1 4 4 

greater: 7 7 7 7 7 7 7 -1 

初期化され、すべての値を持つ唯一のインデックスが6（入力値9）です。

Javaコード：（広範囲にテストされていない）

void find4Numbers(int arr[], int n) 
{ 
    int max = n-1; //Index of maximum element from right side 
    int min = 0, second = -1; //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]; 
    int[] betweenSmallerAndCurrent = new int[n]; 
    smaller[0] = -1; // first entry will always be -1 
    betweenSmallerAndCurrent[0] = -1; 
    for (i = 1; i < n; i++) 
    { 
     if (arr[i] <= arr[min]) 
     { 
      min = i; 
      smaller[i] = -1; 
      betweenSmallerAndCurrent[i] = -1; 
     } 
     else 
     { 
      smaller[i] = min; 
      if (second != -1 && arr[second] < arr[i]) 
      betweenSmallerAndCurrent[i] = second; 
      else 
      betweenSmallerAndCurrent[i] = -1; 
      if (second == -1 || arr[i] < arr[second]) 
      second = i; 
     } 
    } 

    // 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; 
    } 

    // Make sure they're right 
    System.out.println(Arrays.toString(smaller)); 
    System.out.println(Arrays.toString(betweenSmallerAndCurrent)); 
    System.out.println(Arrays.toString(greater)); 

    // 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 (betweenSmallerAndCurrent[i] != -1 && smaller[betweenSmallerAndCurrent[i]] != -1 && greater[i] != -1) 
     { 
      System.out.printf("%d %d %d %d\n", 
          arr[smaller[betweenSmallerAndCurrent[i]]], 
          arr[betweenSmallerAndCurrent[i]], 
          arr[i], 
          arr[greater[i]]); 
      return; 
     } 
    } 

    // If we reach number, then there are no such 3 numbers 
    System.out.println("No such triplet found"); 
} 

あなたは、離れCからJava変換、追加の初期化に、設定ループにあるthisからメインコードを変更することありsmaller。コードは理解しやすいはずです。問題がある場合は、単語に翻訳してみてください。

Test。

Answer 3

大小の配列を持つことは良い選択ですが、スペースが複雑になります。以下は、配列空間を追加せずに線形部分配列内の4つの数を求める解法ですが、定数空間を使用し、配列を1回だけ通過させます。

#include<iostream> 
using namespace std; 


int sortedSubseqFour(int a[], int n) 
{ 
    int small = INT_MAX; 
    int middle_1 = INT_MAX; 
    int middle_2 = INT_MAX; 
    int greater = 0; 


    int main_small = 0; 
    int main_middle_1 = 0; 

    int main_main_small = 0; 

    for(int i = 0; i<n; i++) 
    { 
    if(a[i] <= small) 
     small = a[i]; 

    else if(a[i] <= middle_1) 
    { 
     middle_1 = a[i]; 
     main_small = small; 
    } 

    else if(a[i] <= middle_2) 
    { 
     middle_2 = a[i]; 
     main_middle_1 = middle_1; 
     main_main_small = main_small; 
    } 
    else 
    { 
     greater = a[i]; 
     break; 
    } 
    } 
    //end of loop 

    if(greater!=0) 
    { 
     cout<<"\n"<<main_main_small<<"\t"<<main_middle_1<<"\t"  <<middle_2<<"\t"<<greater<<"\n"; 

    } 
    else 
     cout<<"\n No such Quadruple"; 
    return 1; 
} 

int main() 
{ 
    int arr[20] = {6,7,5,1,4,3,0,7,2,11}; 
    int n = 10; 

    sortedSubseqFour(arr,n); 
    return 0; 
} 

上記のアプローチは、現在の最小値を設定するときに、最小のすべてのレイヤーを覚えています。 'main_main_small'とコードのmiddle_2部分を削除することで、同じコードを配列内のサイズ3のソートされたサブシーケンスに使用することもできます。

同じコードをサイズ 'k'まで拡張し、次に最小iとすると、iの前にあるすべての最小値、すなわちmin_1、min_2、... min_iまでを覚えなければなりません。最後の最小値（つまり、サブシーケンスの最大値）でのみ破棄され、以前または現在の最小値を記憶する必要はありません。

バグが発見された場合はお知らせください。

Answer 4

あなたが最も長いサブシーケンスを見つけ、4以上の大きさであるかどうかを調べることができます（もっと一般的な質問のためにそれを見つける必要がある場合もあります）。最長増加サブシーケンスの長さが4（またはk）未満の場合は、そのようなサブシーケンスが存在しないことを報告できます。 LISは、これはで容易に行うことができる （それが存在する場合）次にグラフと考えると長さkの経路を見つける他の次に大きい要素インデックス-1 を見つけ、各要素についてO(nlog(n))

Answer 5

中で見出すことができますハッシュテーブルとメモを使った線形時間。