綜合應用: 計算軸心點位置 Find the Pivot Integer_Leetcode #2485
題目敘述
題目會給定一個n值，代表區間[1, n]，請問軸心點位置在哪裡?
如果軸心點不存在，返回-1。
軸心點x的定義:
區間1~x的累加總和 = 區間x~n的累加總和。
用虛擬碼描述可以寫成
sum([1, 2, ..., x]) = sum([x, x+1, ..., n])
測試範例
Example 1:
Input: n = 8
Output: 6
Explanation: 6 is the pivot integer since: 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21.
Example 2:
Input: n = 1
Output: 1
Explanation: 1 is the pivot integer since: 1 = 1.
Example 3:
Input: n = 4
Output: -1
Explanation: It can be proved that no such integer exist.
約束條件
Constraints:
1 <= n <= 1000
n值介於1~1000。
演算法 直覺法(也算是暴力展開法)
線性掃描區間內的每個整數i，再用for loop把[1, i]的區間和和[i, n]的區間和算出來。
比較兩者的區間和是否相等。
但是時間複雜度為O(n^2)，有被平台拒絕的風險，
同時暴力展開法也不是一個理想的面試、上機考最終答案。
演算法 直覺法的改良(用數列和公式去計算區間和)
線性掃描區間內的每個整數i，再用數列和公式把[1, i]的區間和和[i, n]的區間和算出來。
比較兩者的區間和是否相等。
時間複雜度為O(n)，算是有進步了，但是還可以更好。
演算法 二分搜尋(用二分搜尋取代線性掃描)
並不需要真正的去try每一個整數i。
當我們知道下區間[1, i]和上區間[i, n]的區間和之後，
只要做個簡單判斷，去決定是否已經找到軸心點，如果還沒找到，也可以知道下一步的搜尋方向。
如果下區間[1, i]的和比較小，代表i還太小，下次二分搜尋[i, n]區間內的數字即可。
如果上區間[i, n]的和比較小，代表i還太大，下次二分搜尋[1, i]區間內的數字即可。
如果下區間[1, i]的和 = 上區間[i, n]的和，那麼i就是軸心點。
時間複雜度為O(log n)，算是很優秀了，也是一個理想的上機考、面試的最終答案。
空間複雜度為O(1)，所用到的都是固定尺寸的臨時變數，為常數級別。
程式碼 二分搜尋(用二分搜尋取代線性掃描)
class Solution:
def rangeSum(self, bottom, top):
# Compute range sum from bottom to top inclusively
return (bottom + top) * ( top - bottom + 1 ) // 2
def pivotInteger(self, n: int) -> int:
lower = 1
upper = n
# Use binary search to find pivot
while( lower <= upper ):
# mid point
mid = (lower + upper) // 2
# range sum from 1 to mid inclusively
lowerSum = self.rangeSum(1, mid)
# range sum from mid to n inclusively
upperSum = self.rangeSum(mid, n)
if lowerSum == upperSum:
return mid
elif lowerSum < upperSum:
lower = mid+1
else:
upper = mid-1
return -1
演算法 解析解(推導軸心點的公式解)
從定義出發
軸心點x的定義:
區間1~x的累加總和 = 區間x~n的累加總和。
用虛擬碼描述可以寫成
sum([1, 2, ..., x]) = sum([x, x+1, ..., n])
下區間[1, x]的和 = 上區間[x, n]的和
可以改寫成
下區間[1, x]的和 = 整體[1, n]的和 - 區間[1, x-1]的和 (這一步算是關鍵步驟)
用數列和公式來表達，可以寫成
[x * (1 + x)] // 2 = [ n*(1+n) ] // 2 - [(x-1) * (x)] // 2
移向後，可以寫成
[x * (1 + x)] // 2 + [(x-1) * (x)] // 2 = [ n*(1+n) ] // 2
等號左邊打開整理後，可得到
x^2 = [ n*(1+n) ] // 2
請留意，到這邊，當初定義的軸心點x已經被我們推出公式解了
x = 開平方根{ [ n*(1+n) ] // 2 } = sqrt{ [ n*(1+n) ] // 2 }
接著，用x^2去驗算是不是恰好的於[ n*(1+n) ] // 2，如果是，x就是軸心點。
為什麼要驗算?
因為開根號之後有可能是得到帶小數點的值，但是，根據定義，軸心點x必須是整數。
時間複雜度為O(1)，算是本題最佳解了，但是上機考/面試時臨場要想到不是這麼容易。
空間複雜度為O(1)，所用到的都是固定尺寸的臨時變數，為常數級別。
程式碼 解析解(推導軸心點的公式解)
class Solution:
def pivotInteger(self, n: int) -> int:
summation = ( n * (n+1) ) // 2
pivot = int( sqrt(summation) )
if pivot ** 2 == summation:
return pivot
else:
return -1
Reference:
