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

我们可以通过扫描数组两次，以 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

设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 回答
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 回答