Вопросы Теги

Как узнать, что тройка треугольников существует в нашем массиве?

Я застрял в решении следующего практического вопроса собеседования:
Мне нужно написать функцию: 

int triangle(int[] A);

, которая для массива A с нулевым индексом, состоящего из N целых чисел, возвращает 1 , если существует тройка (P, Q, R) такая, что 0

. 

A[P] + A[Q] > A[R],  
A[Q] + A[R] > A[P],  
A[R] + A[P] > A[Q].

Функция должна вернуть 0 , если такой тройки не существует. Предположим, что 0 . Предположим, что каждый элемент массива является целым числом в диапазоне [- 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) ). Я думаю, может быть, использовать для хранения дополнительной копии массива и его сортировки, а также использовать двоичный поиск для определенного числа. Но я не знаю, как решить эту проблему.
Есть идеи?

29
задан Martijn Pieters 25 October 2014 в 09:12
поделиться