iT邦幫忙

1

【小馬的LeetCode練功坊】巧妙解法- 差分陣列 1109. Corporate Flight Bookings

今日跟大家分享leetcode上的一道問題,
看似非常簡單,
但時間上壓的很緊,
若沒有使用特別技巧的話便會超時

參考題目: 1109. Corporate Flight Bookings
題意:
總共有n架班機,編號1~n,
我們有許多筆班機座位的訂單,
第i筆訂單bookings[i] = [i, j, k]
意思是訂了班機i~j之間的k個位置。

例如:

Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
Output: [10,55,45,25,25]

我們畫個圖理解一下:
https://ithelp.ithome.com.tw/upload/images/20200524/20117114dVxrYBWTc8.png

題目看起來非常簡單,對吧?
我的第一個想法便是直接跑for迴圈去硬算,
比如說先宣告一個陣列為大小n,
看到每一筆訂單[i, j, k]
就跑for迴圈把陣列[i]~陣列[j]的位置加上k

解法一: 暴力模擬訂票,超時(時間: O(n^2))

我的嘗試如下:

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        ans=[0]*n
        for b in bookings:
            for i in range(b[0],b[1]+1):
                ans[i-1]+=b[2]
        return ans

程式很簡單,但缺點就是如果每一筆訂單座位區間都很大怎麼辦?
比如說總共20000架班機,
每筆訂單都是[1, 19xxx, k]這種形式的,
再給你兩萬筆訂單,
那麼跑for迴圈的時間便大概相當20000 * 20000

本題的精隨便是有沒有辦法只用大概20000次的時間解題?
這題我想了非常久,
想說有可能不用直接去算這個陣列嗎?
畢竟要知道每架班機的座位數量確切是多少耶

後來查詢了別人的參考解法,
覺得此題的解法簡直「妙不可言」

觀念- 差分陣列

這邊要引入一個新的觀念叫「差分陣列」(參考: zerojudge- e340: 差分練習),
給定一個陣列A = {A[0], A[1], A[2], ..., A[n]}
定義陣列B如下:

  • B[0] = A[0]
  • B[i] = A[i] - A[i - 1] for i>0

則B為A的差分陣列,
直覺來看,差分陣列就是原陣列的兩兩項之間的差

解法二: 巧妙,計算差分陣列(時間: O(n))

這一題不可思議的地方在於,
我們不要直接去計算每架班機上有幾個座位,
而去考慮班機座位的「差分陣列」的話,
那麼每筆訂單只需要做2次加法就解決了,
比原本如果每一筆訂單座位區間都很大的情形,
就要相當大量的加法相比,
差分陣列實在非常的妙,

Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
用圖示演示做法:
<原做法>
https://ithelp.ithome.com.tw/upload/images/20200524/20117114ylUB9qZXGm.png

<差分陣列解法>
https://ithelp.ithome.com.tw/upload/images/20200524/20117114abTVlM4csX.png

程式碼(python):

class Solution:
    def corpFlightBookings(self, bookings , n: int):
        diff_arr = [0]*n
        for b in bookings:
            diff_arr[b[0]-1] += b[2]
            if b[1] <n:
                diff_arr[b[1]] -= b[2]             
        result = [] #由差分陣列回推原本的陣列
        for e in diff_arr:
            result.append(e if not result else result[-1]+e)
        return result

順便補個c++程式:

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> diff_arr(n, 0);
        for(auto b: bookings){
            diff_arr[b[0]-1] += b[2];
            if(b[1] <n){
                diff_arr[b[1]] -= b[2];
            }
        }
                   
        vector<int> result(n); //由差分陣列回推原本的陣列
        result[0] = diff_arr[0];
        for(int i=1;i<n;i++){
            result[i]=result[i-1]+diff_arr[i];
        }
        return result;     
    }
};

類似題型

學會這一題還蠻不錯的一點是,
這一題的觀念蠻好用的,
leetcode上有許多類似題型,
等於學了一題就可以舉一反三解開leetcode上很多題

729. My Calendar I
731. My Calendar II
732. My Calendar III
1094. Car Pooling

註: 解題心得- 雖說同樣是用差分陣列的概念,
但略有變化,
如732題的差分陣列大部分項是0,
就適合用有序的map記錄差分陣列的非0項(c++語言用map, python語言用dict),
而不要像1109題開陣列來存

若會解732題,解法可以類推至729, 731, 1094題


尚未有邦友留言

立即登入留言