綜合應用: 計算軸心點位置 Find the Pivot Integer_Leetcode #2485

Modestas Urbonas on Unsplash

題目敘述

題目會給定一個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:

[1] Find the Pivot Integer - LeetCode