查找数组中是否存在元素序列 [英] Find if sequence of elements exists in array

问题描述

是否可以找到数组中的元素序列是否存在?让我们从Pi取得一些数字，

Is it possible to find if a sequence of elements in an array exists? Lets take some digits from the Pi,

 let piDigits=[3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4,3,3,8,3,2,7,9,5,0,2,8,8,4,1,9,7,1,6,9,3,9,9,3,7,5,1,0,5,8,2,0,9,7,4,9,4,4] 

现在，我想查找5和9是否作为数组中的序列元素存在-在这种情况下，它们一次出现在位置4&中.5.

Now, i want to find if, 5 and 9 exist as sequence elements in the array- in this case they do, once, in positions 4 & 5.

理想情况下，我不想使用循环遍历数组，我想要类似于array.contains(element)的东西.

Ideally, i wouldn't like to iterate over the array with a loop, i would like something similar to array.contains(element) .

@Bawpotter，代码段:

@Bawpotter, the code snippet:

 for element in piDigits{  //check every element
  if element == 5 { //if element is equal with the element i want
    var currentPosition = piDigits.index(of: element) //get the position of that element
    if piDigits[currentPosition!+1] == 9 { //if the element at the next position is equal to the other element i want
        print("true")   // it prints true 7 times, instead of 1!
    }
  }
}

推荐答案

使用线性搜索的非常简单的实现:

A very simple implementation using linear search:

let piDigits: [Int] = [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4,3,3,8,3,2,7,9,5,0,2,8,8,4,1,9,7,1,6,9,3,9,9,3,7,5,1,0,5,8,2,0,9,7,4,9,4,4]

let searchedSequence: [Int] = [5, 9]

var index = 0
var resultIndices: [Int] = []

while index < (piDigits.count - searchedSequence.count) {
    let subarray = piDigits[index ..< (index + searchedSequence.count)]

    if subarray.elementsEqual(searchedSequence) {
        resultIndices.append(index)
    }

    index += 1
}

print("Result: \(resultIndices)")

还有其他变体，例如，您可以在迭代期间不断从 piDigits 中删除第一个字符，并检查 piDigits 是否以 searchedSequence开头.

There are other variants as well, you could, for example, keep dropping the first character from piDigits during iteration and check whether piDigits start with the searchedSequence.

如果性能至关重要，我建议您使用字符串搜索算法，例如Aho-Corasick(请参见 https://en.wikipedia.org/wiki/String_searching_algorithm )首先使用状态机进行快速比较(类似于正则表达式).

If performance is critical, I recommend using a string searching algorithm, e.g. Aho-Corasick (see https://en.wikipedia.org/wiki/String_searching_algorithm) which builds a state machine first for fast comparison (similar to regular expressions).

让我们看看如何使用正则表达式:

Let's see how regular expressions can be used:

let searchedSequences: [[Int]] = [[5, 9], [7], [9, 2]]

let stringDigits = piDigits.map { String($0) }.joined()
let stringSearchedSequences = searchedSequences.map { sequence in sequence.map { String($0) }.joined() }

let regularExpressionPattern = stringSearchedSequences.joined(separator: "|")

let regularExpression = try! NSRegularExpression(pattern: regularExpressionPattern, options: [])

let matches = regularExpression.matches(in: stringDigits, options: [], range: NSRange(location: 0, length: stringDigits.characters.count))
let matchedIndices = matches.map { $0.range.location }

print("Matches: \(matchedIndices)")

该方法的缺点是它不会搜索重叠范围(例如，"592"匹配两个范围，但只报告了一个).

The downside of the approach is that it won't search overlapping ranges (e.g. "592" matches two ranges but only one is reported).

这篇关于查找数组中是否存在元素序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！