2

次のようなリストを指定するアルゴリズムを探しています。

[1, 1, 2, 1, 1, 5, 1, 1, 1, 1, 2, 1]

指定された値のすべてのサブシーケンスを検索して返すことができます。たとえば、値 1 が指定された場合、関数は を返し[[1, 1], [1, 1], [1, 1, 1, 1], [1]]ます。

これは、配列のすべてのサブシーケンスを合計したり、特定の文字列のすべてのサブシーケンスを見つけたりするような問題に似ていると思いますが、アルゴリズムは私の得意分野ではありませんでした。答えは、擬似コードまたは言語に依存しない場合があります。よろしければ、ソリューションの複雑さを説明していただけますか?

それが役立つ場合、これが何のために必要かを説明できます。欲しい方はコメントください。

4

3 に答える 3

1

配列を 2 回スキャンすることで、O(n) 時間の複雑さでこれを行うことができます。擬似コード:

//use an array list so we can access element at an index in O(1) time
outputArrays = new ArrayList<int[]> //list of arrays

//loop to declare arrays of outputs - this scans each element once
int currLen = 0;
for (item in inputArray) {
 if (item = itemToLookFor) {
  currLen++;
 }else if (currLen > 0) {
  currLen = 0;
  outputArrays.add(new int[currLen]);
 }
}

//loop to actually populate the output - this scans each element once
currLen = 0;
currIndex = 0;
for (item in inputArray) {
 if (item = itemToLookFor) {
  outputArrays.getElement(currIndex)[currLen] = item;
  currLen++;
 }else if (currLen > 0) {
  currLen = 0;
  currIndex++;
 }
}

明確にできることがあれば教えてください。

于 2016-04-20T04:22:53.603 に答える
0

これがO(n)解決策です。これはシーケンスarrの入力配列でsequence、サブシーケンスの配列です。回答用にシーケンスを別の配列に保存できます。

arr = [1, 1, 2, 1, 1, 5, 1, 1, 1, 1, 2, 1]; // here is your
selectNumber = 1 //take input for selected input
sequence = [];
for (i: 0 to arr.length) {
  if (arr[i] == selectNumber) {
    sequence.push(selectNumber);
  } else {
    if(sequence.length > 0) {
      print sequence;
      sequence = [] // empty sequence array as it is already printed or saved
    }
  }
}

if (sequence > 0) {
  print sequence; // last sequence if exist
}
于 2016-04-20T05:11:31.227 に答える
0

初期a配列、res- シーケンスの結果配列、curSeq- 現在のシーケンス、given_value- 指定された値とします。

res = []
curSeq = []
for i = 1..length(a)
    if a[i] != given_value
        if curSeq has at least one item
            append curSeq to res
        end if
        curSeq = []
    else
        append given_value to curSeq
    end if
end for
if curSeq has at least one item
    append curSeq to res
end if

ご覧のとおり、時間の複雑さはO(n)です。ここで、nは初期配列の長さです。

于 2016-04-20T04:35:12.407 に答える