題目內容
題目頁面: https://app.codility.com/programmers/lessons/6-sorting/triangle/
題意解析
除了任兩邊的長度必須大於第三邊之外,組成三角形的線段還有一些其他的限制:
- 三條邊的長度必須為正數。
- 任兩邊的長度之差必須小於第三邊的長度,也就是說,最長的邊的長度必須小於其他兩邊的長度之和。
- 任何一邊的長度都不能超過其他兩邊長度之和的兩倍。
如果以上任何一個條件不滿足,則無法組成三角形。
0 ≤ P < Q < R < N
解題過程
先寫一個一定會被打槍的暴力解,複雜度為O(N^3)
function solution(A) {
for (let i = 0; i < A.length; i++) {
if (A[i] > 0) {
for (let j = i + 1; j < A.length; j++) {
if (A[j] > 0) {
for (let k = j + 1; k < A.length; k++) {
if (A[k] > 0) {
if (A[i] + A[j] > A[k] &&
A[j] + A[k] > A[i] &&
A[k] + A[i] > A[j]) {
return 1;
}
}
}
}
}
}
return 0;
}
}
結果0%,,沒一個過的了,不是答案錯誤就是runtime error
直覺猜測,這一定和三角形的定義有關,查了一下谷歌大神,找到這段
當一個陣列已經排好序時,如果能夠構成三角形,那麼任意三個相鄰的元素都能構成三角形。
假設排序後的陣列為arr,元素個數為n。我們使用一個for循環遍歷arr中的元素arr[i]。由於arr已經排好序,因此arr[i]一定是arr[i]、arr[i+1]和arr[i+2]中最小的一個,arr[i+1]是中間的一個,arr[i+2]是最大的一個。如果這三個元素能夠構成三角形,那麼其他任意三個相鄰的元素也能構成三角形。
如果arr[i]+arr[i+1]>arr[i+2],那麼一定存在一組三個相鄰的元素可以構成三角形。因此,在檢查完arr[i]、arr[i+1]和arr[i+2]之後,我們可以繼續檢查arr[i+1]、arr[i+2]和arr[i+3],arr[i+2]、arr[i+3]和arr[i+4],以此類推,直到遍歷完整個陣列。
總之,當一個陣列已經排好序時,只需要檢查相鄰的三個元素是否能夠構成三角形,即可判斷是否存在三個元素能夠構成三角形。這比遍歷所有可能的三元組要更高效。
所以就是要知道這個定理就可以了
function solution(A) {
A.sort((a, b) => a - b);
for (let i = 0; i < A.length - 2; i++) {
if (A[i] + A[i + 1] > A[i + 2]) {
return 1;
}
}
return 0;
}
