查找數組中是否存在元素序列

Question

是否有可能找到數組中是否存在元素序列？ 讓我們一些數字，從郫縣，

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] 

現在，我要找到，如果1,5和9存在如在這種情況下，他們這樣做，一旦基於陣列的序列元件，持倉4 & 5.

理想情況下，我不希望與迭代的循環陣列之上，我想類似array.contains（元件）的東西。

@Bawpotter，代碼片段：

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! 
    } 
    } 
} 

Answer 1

使用線性搜索一個非常簡單的實現：

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開頭。

如果性能很關鍵，我推薦使用字符串搜索算法，例如， Aho-Corasick（見https://en.wikipedia.org/wiki/String_searching_algorithm）首先構建一個狀態機用於快速比較（類似於正則表達式）。

讓我們來看看如何表達經常可用於：

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」匹配兩個範圍，但只有一個報道）。

Answer 2

let firstSeqNum = 5 
let secondSeqNum = 9 
for (index, number) in array.enumerated() { 
    if number == firstSeqNum && array[index+1] == secondSeqNum { 
     print("The sequence \(firstSeqNum), \(secondSeqNum) was found, starting at an index of \(index).") 
    } 
} 

既然有這個沒有內置的方法，這將是你最好的選擇。

Answer 3

裏面包含迭代方法在陣列上，在這裏你必須做同樣的事情。下面一個例子：

extension Array where Element: Equatable { 
    func contains(array elements: [Element]) -> Int { 
    guard elements.count > 0 else { return 0 } 
    guard count > 0 else { return -1 } 

    var ti = 0 

    for (index, element) in self.enumerated() { 
     ti = elements[ti] == element ? ti + 1 : 0 

     if ti == elements.count { 
     return index - elements.count + 1 
     } 
    } 

    return -1 
    } 
} 

這裏如何使用它：

let index = [1, 4, 5, 6, 6, 9, 6, 8, 10, 3, 4].contains(array: [6, 8, 10]) 
// index = 6 

let index = [1, 4, 5, 6, 6, 9, 6, 8, 10, 3, 4].contains(array: [6, 8, 1]) 
// index = -1