1

Недавно на собеседовании попалась задачка, где нужно было переписать метод так, чтобы он работал быстро и на больших входных данных.

public int solution (int[] A){
    N = A.length;
    result = 0;
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            if (A[i] != A[j])
                result = Math.max(result, j - i);
        }
    }
    return result;
}

Буду благодарен, если подтолкнете в нужном направлении как это решать.

2 ответа 2

4

Если посмотреть на код, то результат - максимальное расстояние между 2 неодинаковыми элементами.

Не трудно заметить, что один из этих 2 элементов будет крайний слева или крайний справа. Дальше просто реализация за O(N) в худшем случае.

6
  • Меня программная реализация и волнует. Покажите, пожалуйста, как можно перестроить метод?
    – exStas
    23 мая 2016 в 14:10
  • @exStas вы не смогли реализовать то что я написал? Вы точно поняли мой ответ?
    – pavel
    23 мая 2016 в 14:13
  • Чисто для себя - в конечном итоге это означает. зафиксировать один из концов и одним проходом по массиву, с противоположной стороны. проверять значения сравнивая с данным элементом ?
    – xAqweRx
    24 мая 2016 в 6:21
  • @xAqweRx да, так. Только странное задание - solution фактически считает длину массива, то есть расстояние между 1-м и последним элементом. Тогда можно вообще убрать двойной цикл и оставить result = A.Length - 1 :)
    – Denis
    24 мая 2016 в 6:27
  • Это только в том случае. если они все разные. Но в случае, если значения одинаковы - тут начинается уже вопрос.
    – xAqweRx
    24 мая 2016 в 6:44
0

Если кто-то не разобрался, то вот готовое решения (как получилось у меня):

public static int solution(int data[])
{
    int result = 0;

    int count = data.length;
    for (int i = 1; i < count; i++)
    {
        if (data[i - 1] != data[i] || data[i - 1] != data[count - i])
        {
            result = Math.max(result, count - i);
        }
    }

    return result;
}

UPD: Все же есть проблема, не доглядел все моменты.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

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