每日算法：有效三角形的個(gè)數(shù)
本文轉(zhuǎn)載自微信公眾號(hào)「三分鐘學(xué)前端」，作者sisterAn。轉(zhuǎn)載本文請聯(lián)系三分鐘學(xué)前端公眾號(hào)。
給定一個(gè)包含非負(fù)整數(shù)的數(shù)組，你的任務(wù)是統(tǒng)計(jì)其中可以組成三角形三條邊的三元組個(gè)數(shù)。
示例 1:
- 輸入: [2,2,3,4]
- 輸出: 3
- 解釋:
- 有效的組合是:
- 2,3,4 (使用第一個(gè) 2)
- 2,3,4 (使用第二個(gè) 2)
- 2,2,3
注意:
- 數(shù)組長度不超過1000。
- 數(shù)組里整數(shù)的范圍為 [0, 1000]。
解法：排序+雙指針
我們知道三角形的任意兩邊之和大于第三邊，任意兩邊之差小于第三邊，如果這三條邊長從小到大為 a 、 b 、 c ，當(dāng)且僅當(dāng) a + b > c 這三條邊能組成三角形
解題思路： 先數(shù)組排序，排序完后，固定最長的邊，利用雙指針法判斷其余邊
以 nums[nums.length - 1] 作為最長的邊 nums[k] ( k = nums.length - 1 )
以 nums[i] 作為最短邊，以 nums[nums.length - 2] 作為第二個(gè)數(shù) nums[j] ( j = nums.length - 2 ) ，
判斷 nums[i] + nums[j] 是否大于 nums[k] ，
- nums[i] + nums[j] > nums[k] ，則：
- nums[i+1] + nums[j] > nums[k]
- nums[i+2] + nums[j] > nums[k]
- ...
- nums[j-1] + nums[j] > nums[k]
則可構(gòu)成三角形的三元組個(gè)數(shù)加 j-i ，并且 j 往前移動(dòng)一位( j-- )， 繼續(xù)進(jìn)入下一輪判斷
- nums[i] + nums[j] <= nums[k]，則 l 往后移動(dòng)一位(nums 是增序排列)，繼續(xù)判斷
代碼實(shí)現(xiàn)：
- let triangleNumber = function(nums) {
- if(!nums || nums.length < 3) return 0
- let count = 0
- // 排序
- nums.sort((a, b) => a - b)
- for(let k = nums.length - 1; k > 1; k--){
- let i = 0, j = k - 1
- while(i < j){
- if(nums[i] + nums[j] > nums[k]){
- count += j - i
- j--
- } else {
- i++
- }
- }
- }
- return count
- }
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：O(n^2^)
- 空間復(fù)雜度：O(n)
注意：
關(guān)于 Array.prototype.sort() ，ES 規(guī)范并沒有指定具體的算法，在 V8 引擎中， 7.0 版本之前，數(shù)組長度小于10時(shí)， Array.prototype.sort() 使用的是插入排序，否則用快速排序。
在 V8 引擎 7.0 版本之后就舍棄了快速排序，因?yàn)樗皇欠€(wěn)定的排序算法，在最壞情況下，時(shí)間復(fù)雜度會(huì)降級(jí)到 O(n2)。
而是采用了一種混合排序的算法：TimSort 。
這種功能算法最初用于Python語言中，嚴(yán)格地說它不屬于以上10種排序算法中的任何一種，屬于一種混合排序算法：
在數(shù)據(jù)量小的子數(shù)組中使用插入排序，然后再使用歸并排序?qū)⒂行虻淖訑?shù)組進(jìn)行合并排序，時(shí)間復(fù)雜度為 O(nlogn) 。
leetcode：https://leetcode-cn.com/problems/valid-triangle-number/solution/teng-xun-leetcode611you-xiao-san-jiao-xing-de-ge-s/
