Как написать функцию есть ли в массиве два подряд равных идущих элемента

Алгоритм проверки на наличие двух подряд идущих равных элементов

Для решения задачи о наличии двух последовательных равных элементов в массиве можно использовать несколько подходов. Рассмотрим наиболее эффективные и практичные варианты.

Базовый алгоритм с линейным проходом

Самый простой и эффективный способ — пройти по массиву один раз, сравнивая каждый элемент с его соседом справа.

fun hasConsecutiveDuplicates(arr: IntArray): Boolean {
    // Проверяем массив на наличие хотя бы двух элементов
    if (arr.size < 2) {
        return false
    }
    
    // Проходим по массиву, сравнивая текущий элемент со следующим
    for (i in 0 until arr.size - 1) {
        if (arr[i] == arr[i + 1]) {
            return true // Нашли два подряд равных элемента
        }
    }
    
    return false // Не нашли последовательных дубликатов
}

Универсальная функция для любых типов данных

Для большей гибкости можно создать обобщенную функцию, которая будет работать с любым типом данных, реализующим интерфейс Comparable:

fun <T> hasConsecutiveDuplicatesGeneric(arr: Array<T>): Boolean {
    if (arr.size < 2) return false
    
    for (i in 0 until arr.size - 1) {
        if (arr[i] == arr[i + 1]) {
            return true
        }
    }
    
    return false
}

Решение с использованием стандартных функций Kotlin

Kotlin предоставляет элегантные средства для работы с коллекциями. Вот несколько вариантов с использованием стандартных функций:

// Вариант 1: Использование windowed()
fun hasConsecutiveDuplicatesKotlin1(arr: IntArray): Boolean {
    return arr.asSequence()
        .windowed(2)
        .any { it[0] == it[1] }
}

// Вариант 2: Использование zipWithNext()
fun hasConsecutiveDuplicatesKotlin2(arr: IntArray): Boolean {
    return arr.zipWithNext().any { (first, second) -> first == second }
}

// Вариант 3: Использование индексов и firstOrNull
fun hasConsecutiveDuplicatesKotlin3(arr: IntArray): Boolean {
    return (0 until arr.size - 1)
        .firstOrNull { arr[it] == arr[it + 1] } != null
}

Оптимизация и особенности реализации

При реализации такой функции стоит учитывать несколько важных аспектов:

1. Проверка граничных условий: Всегда проверяйте размер массива. Для массива из 0 или 1 элемента функция должна возвращать false.

2. Эффективность алгоритма:

   • Временная сложность: O(n), где n — количество элементов в массиве
   • Пространственная сложность: O(1) для базового алгоритма

3. Обработка null-значений (если работаем с nullable типами):

fun hasConsecutiveDuplicatesNullable(arr: Array<Int?>): Boolean {
    if (arr.size < 2) return false
    
    for (i in 0 until arr.size - 1) {
        // Используем безопасное сравнение
        if (arr[i] == arr[i + 1]) {
            return true
        }
    }
    
    return false
}

Примеры использования

fun main() {
    // Тестовые случаи
    val test1 = intArrayOf(1, 2, 3, 4, 5) // false
    val test2 = intArrayOf(1, 2, 2, 3, 4) // true
    val test3 = intArrayOf(1) // false
    val test4 = intArrayOf() // false
    val test5 = intArrayOf(5, 5, 5, 5) // true
    
    println("Test 1: ${hasConsecutiveDuplicates(test1)}") // false
    println("Test 2: ${hasConsecutiveDuplicates(test2)}") // true
    println("Test 3: ${hasConsecutiveDuplicatesKotlin1(test3)}") // false
    println("Test 4: ${hasConsecutiveDuplicatesKotlin2(test4)}") // false
    println("Test 5: ${hasConsecutiveDuplicatesKotlin3(test5)}") // true
}

Выбор подхода

Рекомендации по выбору реализации:

1. Для простых случаев — используйте базовый алгоритм с циклом for. Он наиболее читаем и эффективен.
2. Для работы с разными типами данных — создайте обобщенную функцию.
3. В функциональном стиле Kotlin — используйте zipWithNext() или windowed(), которые делают код более декларативным.
4. Для больших массивов — базовый алгоритм предпочтительнее из-за минимальных накладных расходов.

Ключевые моменты для собеседования:

• Подчеркните важность проверки граничных условий
• Объясните временную и пространственную сложность алгоритма
• Покажите знание стандартных функций Kotlin
• Упомяните возможность оптимизации для конкретных сценариев (например, если массив отсортирован)

Это задание проверяет понимание основ алгоритмов, работу с массивами и знание особенностей языка Kotlin, что является важным для Android-разработчика.