算法筆試模拟題精解之“吃奶酪”

線上程式設計介紹

阿裡雲開發者社群線上程式設計産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，為使用者營造專心答題的學習環境。點選連結開始體驗：

https://developer.aliyun.com/coding

本文為大家介紹其中的 第49題：吃奶酪 的題目解析，具體如下：

題目描述

題目等級：容易

知識點：貪心、枚舉

檢視題目：吃奶酪

Tom和Jerry都很喜歡吃奶酪，現在有n塊奶酪散落在坐标軸上(1<=n<=100000)，他們分别在a1,a2,a3...an(1<=ai<=100000,一個點可以有多塊奶酪)上，Tom和Jerry分别在1和100000兩個點上，他們每走一步需要花費1s，問他們拿到所有的奶酪至少要花費多少時間

輸入奶酪數量n，和n個奶酪的坐标

輸出一個數，表示他們拿到所有奶酪所用的最短時間

示例1

輸入：

4

[350,2000,80000,99999]

輸出：

20000

解題方法

根據題意，如果要花費最少時間，則每個奶酪都讓離奶酪最近的人去拿，是以，坐标<=50000的奶酪讓Tom去拿，坐标>=50001的奶酪讓Jerry去拿。

具體實作時，可以設定一個time值，然後周遊數組。判斷每一塊奶酪的坐标範圍，根據坐标判斷應該讓誰拿，再計算拿到這個奶酪需要多長時間，如果時間大于time，則用這個值替換掉time的值。

用這種方法，周遊整個數組後的time值即為 Tom 和 Jerry 拿到所有奶酪所用的最短時間。

時間複雜度：O(n)

空間複雜度：O(1)

看完之後是不是有了想法了呢，快來練練手吧>>