← Static tasks

1095. Find in Mountain Array

leetcode hard

#array#csharp#hard#leetcode#search#two-pointers

Task

Массив arr является горным массивом тогда и только тогда, когда:

Длина массива arr >= 3.

Существует некоторое i с 0 < i < arr.length - 1 такое, что:

arr[0] < arr[1] < ... < arr[i - 1] < arr[i]

arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Дан горный массив mountainArr, верните минимальный индекс, такой что mountainArr.get(index) == target. Если такого индекса не существует, верните -1.

Вы не можете напрямую обращаться к массиву. Вы можете использовать интерфейс MountainArray:

MountainArray.get(k) возвращает элемент массива на индексе k (индексация начинается с 0).

MountainArray.length() возвращает длину массива.

Решения, использующие более 100 вызовов MountainArray.get, будут оценены как неправильные. Также любые решения, которые пытаются обойти ограничение, будут дисквалифицированы.

Пример:

Input: array = [1,2,3,4,5,3,1], target = 3

Output: 2

Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.

C# solution

matched/original
public class Solution {
    public int FindInMountainArray(int target, MountainArray mountainArr) {
        int length = mountainArr.length();
        int low = 1, high = length - 2;
        while (low != high) {
            int mid = (low + high) / 2;
            if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        int peak = low;
        low = 0;
        high = peak;
        while (low < high) {
            int mid = (low + high) / 2;
            if (mountainArr.get(mid) < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        if (mountainArr.get(low) == target) {
            return low;
        }
        low = peak + 1;
        high = length - 1;
        while (low < high) {
            int mid = (low + high) / 2;
            if (mountainArr.get(mid) > target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        if (mountainArr.get(low) == target) {
            return low;
        }
        return -1;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int FindInMountainArray(int target, MountainArray mountainArr) {
        int length = mountainArr.length();
        int low = 1, high = length - 2;
        while (low != high) {
            int mid = (low + high) / 2;
            if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        int peak = low;
        low = 0;
        high = peak;
        while (low < high) {
            int mid = (low + high) / 2;
            if (mountainArr.get(mid) < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        if (mountainArr.get(low) == target) {
            return low;
        }
        low = peak + 1;
        high = length - 1;
        while (low < high) {
            int mid = (low + high) / 2;
            if (mountainArr.get(mid) > target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        if (mountainArr.get(low) == target) {
            return low;
        }
        return -1;
    }
}

Java solution

matched/original
class Solution {
    public int findInMountainArray(int target, MountainArray mountainArr) {
        int length = mountainArr.length();

        int low = 1;
        int high = length - 2;
        while (low != high) {
            int mid = (low + high) / 2;
            if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        int peak = low;

        low = 0;
        high = peak;
        while (low < high) {
            int mid = (low + high) / 2;
            if (mountainArr.get(mid) < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        if (mountainArr.get(low) == target) {
            return low;
        }

        low = peak + 1;
        high = length - 1;
        while (low < high) {
            int mid = (low + high) / 2;
            if (mountainArr.get(mid) > target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        if (mountainArr.get(low) == target) {
            return low;
        }

        return -1;
    }
}

JavaScript solution

matched/original
var findInMountainArray = function(target, mountainArr) {
    const length = mountainArr.length()

    let low = 1, high = length - 2
    while (low != high) {
        const mid = Math.floor((low + high) / 2)
        if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
            low = mid + 1
        } else {
            high = mid
        }
    }
    const peak = low

    low = 0
    high = peak
    while (low < high) {
        const mid = Math.floor((low + high) / 2)
        if (mountainArr.get(mid) < target) {
            low = mid + 1
        } else {
            high = mid
        }
    }
    if (mountainArr.get(low) == target) {
        return low
    }

    low = peak + 1
    high = length - 1
    while (low < high) {
        const mid = Math.floor((low + high) / 2)
        if (mountainArr.get(mid) > target) {
            low = mid + 1
        } else {
            high = mid
        }
    }
    if (mountainArr.get(low) == target) {
        return low
    }

    return -1
}

Go solution

matched/original
type MountainArray struct {
    get    func(int) int
    length func() int
}

func findInMountainArray(target int, mountainArr *MountainArray) int {
    length := mountainArr.length()

    low, high := 1, length-2
    for low != high {
        mid := (low + high) / 2
        if mountainArr.get(mid) < mountainArr.get(mid+1) {
            low = mid + 1
        } else {
            high = mid
        }
    }
    peak := low

    low, high = 0, peak
    for low < high {
        mid := (low + high) / 2
        if mountainArr.get(mid) < target {
            low = mid + 1
        } else {
            high = mid
        }
    }
    if mountainArr.get(low) == target {
        return low
    }

    low, high = peak + 1, length-1
    for low < high {
        mid := (low + high) / 2
        if mountainArr.get(mid) > target {
            low = mid + 1
        } else {
            high = mid
        }
    }
    if mountainArr.get(low) == target {
        return low
    }

    return -1
}

Explanation

Algorithm

Найти индекс пика: Инициализируем два указателя low и high, где low начинается с 1, а high — с длины массива минус 2. Используем бинарный поиск для нахождения пикового элемента: если элемент в середине меньше следующего элемента, то пиковый элемент находится справа, иначе он находится слева. Продолжаем сужать диапазон поиска до тех пор, пока low не станет равным high. Это и будет индекс пика.

Бинарный поиск в возрастающей части массива: Устанавливаем указатели low и high для поиска в диапазоне от 0 до пикового индекса. Проводим обычный бинарный поиск: если значение в середине меньше целевого значения, перемещаем low вправо, иначе перемещаем high влево. По завершении поиска проверяем, равно ли значение по индексу low целевому значению. Если да, возвращаем индекс, иначе продолжаем.

Бинарный поиск в убывающей части массива: Устанавливаем указатели low и high для поиска в диапазоне от пикового индекса плюс 1 до конца массива. Проводим бинарный поиск, но с учетом убывающей последовательности: если значение в середине больше целевого значения, перемещаем low вправо, иначе перемещаем high влево. По завершении поиска проверяем, равно ли значение по индексу low целевому значению. Если да, возвращаем индекс. Если значение не найдено, возвращаем -1.

😎