Кратчайший способ найти повторяющиеся непрерывные значения в массиве

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, поэтому функция должна вернуть 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

Я сделал карту сокращения для нахождения максимально возможного результата, я добавил перечислимую карту в массив Int для получения значения его индекса внутри карты уменьшения, весь код протестирован с 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 { ($0, $1) }

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 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 { ($0, $1) }

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 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
)

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

Вы можете реализовать эту функцию, она вернет вам массив словарей, и я думаю, у вас будет лучшее представление о том, как с этим справиться.

extension Array where Element: Hashable {
    var occurrences: [Element:Int] {
        return reduce(into: [:]) { $0[$1, 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 раза и т. Д.