Я застрял в решении следующего вопроса практики интервью:
Мне нужно написать функцию:
int triangle(int[] A);
что для нулевого индекса массива A, состоящего из N
integers, возвращается 1
, если существует тройка (P, Q, R) такая, что 0 < P < Q < R < N
.
A[P] + A[Q] > A[R],
A[Q] + A[R] > A[P],
A[R] + A[P] > A[Q].
Функция должна возвращать 0
, если такая тройка не существует. Предположим, что 0 < N < 100,000
. Предположим, что каждый элемент массива является целым числом в диапазоне [-1,000,000..1,000,000]
.
Например, данный массив A
такой, что
A[0]=10, A[1]=2, A[2]=5, A[3]=1, A[4]=8, A[5]=20
функция должна возвращать 1
, потому что тройка (0, 2, 4)
выполняет все необходимые условия.
Для массива A
такого, что
A[0]=10, A[1]=50, A[2]=5, A[3]=1
функция должна возвращать 0
.
Если я делаю тройной цикл, это будет очень очень медленно (сложность: O(n^3)
). Я думаю, возможно, использовать для хранения дополнительной копии массива и сортировки его, а также использовать двоичный поиск для определенного числа. Но я не знаю, как разрушить эту проблему.
Любые идеи?