4

Есть массив 1 2 3 ... N. Известно, что этот массив можно разбить на три интервала [1 2 .. .L-2 L-1], [L L+1 ... R-1 R], [R+1 R+2 ... N-1 N], (L<=R) так что каждый элемент из своего интервала дает определенный результат в функции f. f(1)=f(2)=...f(L-1), f(L)=f(L+1)=...f(R). f(R+1)=f(R+2)=...f(N).

Как за logN (какой-нибудь модифицированный бинарный поиск) найти эти L и R?

4
  • Нужно найти сам интервал или его длинну?
    – talex
    3 янв 2019 в 6:32
  • Я кажется понял. Тут нужно два бинарных поиска. Для начала интервала и для конца.
    – talex
    3 янв 2019 в 7:29
  • Объясню поподробнее. Есть массив 1 2 3 ... N. Известно, что этот массив можно разбить на три интервала [1 2 .. .L-2 L-1], [L L+1 ... R-1 R], [R+1 R+2 ... N-1 N], (L<=R) так что каждый элемент из своего интервала дает определенный результат в функции f. f(1)=f(2)=...f(L-1) f(L)=f(L+1)=...f(R) f(R+1)=f(R+2)=...f(N). Как за logN (какой-нибудь модифицированный бинарный поиск) найти эти L и R? 3 янв 2019 в 7:38
  • @talex Да, что-то в этом роде. Мне нужен пример кода правда. 3 янв 2019 в 7:41

1 ответ 1

4

Извиняюсь что на Джаве.

public class App {
    public static void main(String[] args) {

        int[] arr = {1,1,2,2,2,2,3,3};

        Interval interval = find(0, arr.length - 1, i -> arr[i]);

        System.out.println(interval);

    }

    static Interval find(int start, int finish, Function<Integer, Object> f) {
        int intStart = findStart(start, finish, f) + 1;
        int intEnd = findStart(intStart, finish, f);
        return new Interval(intStart, intEnd);
    }

    private static int findStart(int start, int finish, Function<Integer, Object> f) {
        int a = start;
        int b = finish;
        Object aO = f.apply(start);
        Object bO = f.apply(finish);
        while (a + 1 < b) {
            int m = (a + b) / 2;
            Object mO = f.apply(m);
            if (aO.equals(mO)) {
                a = m;
            } else {
                assert bO.equals(mO);
                b = m;
            }
        }
        return a;
    }

    @Data
    private static class Interval {
        private final int intStart;
        private final int intEnd;
    }
}
1
  • Надо еще потестить на граничные условия.
    – talex
    3 янв 2019 в 7:46

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.