在数组中查找重复连续值的最短方法

Question

我有一个数组

[1,5,3,3,4,4,4,5,6,6,6,6,8,9,1,1,5]

这里，'4'连续重复3次，'6'连续重复4次。数组长度不固定。

所以我需要迭代这个数组来找到连续重复的最大数量。因此，4 和 6 都在重复，但最高的是 6，因此函数应该 return 6 及其起始索引和结束索引在短时间内。

我也有案例2。

[10,11,10,10,11,10,15,16,20,21,22,21,21,20,20]

在上述情况下，数值之间的微小差异可以忽略不计。例如。第一个序列有 10,11,10,10,11,10，第二个序列有 20,21,22,21,21,20,20，最高重复值将是 第二个序列

如果公差为 1，则将考虑第一种情况而不是第二种情况。因为如果公差为 1，那么第二个序列将是 [21,21,20,20]，因此出现的最大次数（计数）是第一种情况。

如有任何帮助，我们将不胜感激。

Answer 1

你可以实现这个功能，它会return你的字典数组，我想你会更好地知道如何处理它。

extension Array where Element: Hashable {
    var occurrences: [Element:Int] {
        return reduce(into: [:]) { [=10=][, default: 0] += 1 }
    }
}

让我们有一个这样的数组，

let numbers = [1,5,3,3,4,4,4,5,6,6,6,6,8,9,1,1,5]
print(numbers.occurrences)

输出会是这样的，

[4: 3, 9: 1, 5: 3, 6: 4, 3: 2, 8: 1, 1: 3]

表示4重复3次，9重复1次，5重复3次，以此类推..

Answer 2

    let array = [1,5,3,3,4,4,4,5,6,6,6,6,8,9,1,1,5]

    var maxNum = Int.max
    var maxCount = 0
    var currentNum = Int.max
    var currentCount = 0

    print("start")

    for num in array {
        print("cycle")
        if currentNum == num {
            currentCount += 1
        } else {
            if currentCount > maxCount {
                maxCount = currentCount
                maxNum = currentNum
            }
            currentNum = num
            currentCount = 1
        }
    }

    print("max count is \(maxCount) with num \(maxNum)")

不太优雅，但工作

Answer 3

情况 2 使事情变得更加复杂（即，如果您引入一些容差，您可能必须跟踪多个子序列作为最佳候选）。但 FWIW 这是我对原始问题的解决方案：

func mostRepeatedElement(in array: [Int]) -> (best: Int, count: Int)? {
    guard let first = array.first else {
        return nil
    }

    var best = first
    var bestCount = 0
    var currentCount = 0
    var previous: Int?

    for current in array {
        defer { previous = current }

        if current == previous {
            currentCount += 1
        } else {
            currentCount = 1
        }

        if currentCount > bestCount {
            best = current
            bestCount = currentCount
        }
    }

    return (best, bestCount)
}

它与@AntiVIRUZ 的相似，但似乎也适用于具有零个或一个元素的数组。

Answer 4

我制作了一个 reduce map 来查找最大出现结果，我在 Int 数组中添加了一个枚举 map 以获取它在 reduce map 中的索引值，所有代码都使用 Swift 4 进行了测试.

排序方式：

let array: [(Int, Int)] = [1, 5, 3, 3, 4, 4, 4, 5, 6, 6, 6, 6, 8, 9, 1, 1, 5].enumerated().map { ([=10=], ) }

var results: [Result] = []

guard let maxResult = array.reduce(nil, { (maxResult, item) -> Result? in
    let (index, value) = item
    guard let result = results.first(where: { (result) -> Bool in
        result.value == value && result.endIndex + 1 == index
    }) else {
        let result = Result(value, startIndex: index)
        results.append(result)
        return result > maxResult ? result : maxResult
    }
    result.endIndex = index
    return result > maxResult ? result : maxResult
}) else {
    print("no max result found :(")
    return
}

print("found max result: \(maxResult) in results: \(results)")

结果class:

class Result {
    let value: Int
    var numberOfOcurrences: Int
    let startIndex: Int
    var endIndex: Int {
        didSet {
            numberOfOcurrences += 1
        }
    }

    init(_ value: Int, startIndex: Int) {
        self.value = value
        self.startIndex = startIndex
        self.endIndex = startIndex
        self.numberOfOcurrences = 1
    }

    static func > (lhs: Result, rhs: Result?) -> Bool {
        return lhs.numberOfOcurrences > rhs?.numberOfOcurrences ?? 0
    }
}

extension Result: CustomStringConvertible {

    var description: String {
        return """
        Result(
            value: \(value),
            numberOfOcurrences: \(numberOfOcurrences),
            startIndex: \(startIndex),
            endIndex: \(endIndex)
        )
        """
    }
}

输出：

/*  output: found max result: Result(
            value: 6,
            numberOfOcurrences: 4,
            startIndex: 8,
            endIndex: 11
        ) in results: [
            Result(
                value: 1,
                numberOfOcurrences: 1,
                startIndex: 0,
                endIndex: 0
            ),
            Result(
                value: 5,
                numberOfOcurrences: 1,
                startIndex: 1,
                endIndex: 1
            ),
            Result(
                value: 3,
                numberOfOcurrences: 2,
                startIndex: 2,
                endIndex: 3
            ),
            Result(
                value: 4,
                numberOfOcurrences: 3,
                startIndex: 4,
                endIndex: 6
            ),
            Result(
                value: 5,
                numberOfOcurrences: 1,
                startIndex: 7,
                endIndex: 7
            ),
            Result(
                value: 6,
                numberOfOcurrences: 4,
                startIndex: 8,
                endIndex: 11
            ),
            Result(
                value: 8,
                numberOfOcurrences: 1,
                startIndex: 12,
                endIndex: 12
            ),
            Result(
                value: 9,
                numberOfOcurrences: 1,
                startIndex: 13,
                endIndex: 13
            ),
            Result(
                value: 1,
                numberOfOcurrences: 2,
                startIndex: 14,
                endIndex: 15
            ),
            Result(
                value: 5,
                numberOfOcurrences: 1,
                startIndex: 16,
                endIndex: 16
            )
        ]
    */

更新：案例 2

let array: [(Int, Int)] = [10, 11, 10, 10, 11, 10, 15, 16, 20, 21, 22, 21, 21, 20, 20].enumerated().map { ([=13=], ) }

var results: [Result] = []
let tolerance: Int = 1 // now there can be one other in between

guard let maxResult = array.reduce(nil, { (maxResult, item) -> Result? in
   let (index, value) = item
    guard let result = results.first(where: { (result) -> Bool in
        return result.value == value && result.endIndex + (1 + tolerance) >= index
    }) else {
        let result = Result(value, startIndex: index)
        results.append(result)
        return result > maxResult ? result : maxResult
    }
    result.endIndex = index
    return result > maxResult ? result : maxResult
}) else {
    print("no max result found :(")
    return
}

print("found max result: \(maxResult) in results: \(results)")

输出：

/*  output: found max result: Result(
            value: 10,
            numberOfOcurrences: 4,
            startIndex: 0,
            endIndex: 5
        ) in results: [
            Result(
                value: 10,
                numberOfOcurrences: 4,
                startIndex: 0,
                endIndex: 5
            ), Result(
                value: 11,
                numberOfOcurrences: 1,
                startIndex: 1,
                endIndex: 1
            ), Result(
                value: 11,
                numberOfOcurrences: 1,
                startIndex: 4,
                endIndex: 4
            ), Result(
                value: 15,
                numberOfOcurrences: 1,
                startIndex: 6,
                endIndex: 6
            ), Result(
                value: 16,
                numberOfOcurrences: 1,
                startIndex: 7,
                endIndex: 7
            ), Result(
                value: 20,
                numberOfOcurrences: 1,
                startIndex: 8,
                endIndex: 8
            ), Result(
                value: 21,
                numberOfOcurrences: 3,
                startIndex: 9,
                endIndex: 12
            ), Result(
                value: 22,
                numberOfOcurrences: 1,
                startIndex: 10,
                endIndex: 10
            ), Result(
                value: 20,
                numberOfOcurrences: 2,
                startIndex: 13,
                endIndex: 14
            )
        ]
    */

更新 3：编辑结果 class 以按顺序存储值的数量

class Result {
    let value: Int
    var numberOfOcurrences: Int
    var numberOfValuesInSequence: Int
    let startIndex: Int
    var endIndex: Int {
        didSet {
            numberOfOcurrences += 1
            numberOfValuesInSequence = (endIndex - startIndex) + 1
        }
    }

    init(_ value: Int, startIndex: Int) {
        self.value = value
        self.startIndex = startIndex
        self.endIndex = startIndex
        self.numberOfOcurrences = 1
        self.numberOfValuesInSequence = 1
    }

    static func > (lhs: Result, rhs: Result?) -> Bool {
        return lhs.numberOfValuesInSequence > rhs?.numberOfValuesInSequence ?? 0
    }
}

extension Result: CustomStringConvertible {

    var description: String {
        return """
        Result(
            value: \(value),
            numberOfOcurrences: \(numberOfOcurrences),
            numberOfValuesInSequence: \(numberOfValuesInSequence),
            startIndex: \(startIndex),
            endIndex: \(endIndex)
        )
        """
    }
}

输出：

Result(
    value: 10,
    numberOfOcurrences: 4,
    numberOfValuesInSequence: 6,
    startIndex: 0,
    endIndex: 5
)

在数组中查找重复连续值的最短方法

Shortest way to find repetitive continuous values in an array

arrays

sequences

swift