B*******1
发帖数: 2454 | 1 不知道哪个公司的
Write a function
int triangle(int A[], int n);
which given a zero-indexed array A of n integers returns 1 if there exists
triple i,j,k ($i\not=j\not=k$, $0\le i,j,k
A[i] + A[j] > A[k]
A[i] + A[k] > A[j]
A[j] + A[k] > A[i]
or returns 0 otherwise.
Examples:
For:
A[0]=10, A[1]=2, A[2]=5, A[3]=1, A[4]=8, A[5]=20
your function should return 1, since for i=0,j=2,k=4 all conditions are
fullfiled (i.e. A[2]+A[4]>A[0]).
For:
A[0]=10, A[1]=50, A[2]=5, A[3]=1
your function should return 0. | r*******g
发帖数: 1335 | 2 The direct method is to sort it in decending order.
a1>a2>a3>.....Then find the first one a1
If none of this exist, return false.
Probably other method exist. | r*******y
发帖数: 1081 | 3 time complexity is n^2 * log(n) ?
【在 r*******g 的大作中提到】
: The direct method is to sort it in decending order.
: a1>a2>a3>.....Then find the first one a1: If none of this exist, return false.
: Probably other method exist.
| r*******g
发帖数: 1335 | 4 不是啊，sort是O(nlogn)，sort好之后依次遍历就行，是O(n)
关键就是，如果ak>a_(k+1)+a_(k+2)，那么ak肯定落选，因为整个数组是sort好了的。
【在 r*******y 的大作中提到】
: time complexity is n^2 * log(n) ?
| c*********t
发帖数: 2921 | 5 是不是这个题要假设所有的数都是正的。负的话，你的算法很难work。
【在 r*******g 的大作中提到】
: The direct method is to sort it in decending order.
: a1>a2>a3>.....Then find the first one a1: If none of this exist, return false.
: Probably other method exist.
|
|
