筆試算法模拟題精解之“ 最優分組”

【線上程式設計産品介紹】

阿裡雲開發者社群線上程式設計：

免費刷題大神器，助你拿到好offer

周賽月賽不停歇，做題還能領獎品

大賽筆試全真題，常做常新有驚喜

點選連結開始産品體驗：

https://developer.aliyun.com/coding

本文為大家介紹的是“132.最優分組”的解法探究。先來看一下題目内容：

等級：容易

知識點：尺取法

檢視題目：最優分組

給出一個長度為 n 的數組和一個數字 k ，你需要在數組中選出一些數字，這些數字兩兩之間的內插補點不能超過k。你需要判斷最多能夠挑出的數字個數。（n在[1, 100000]之間，k和數組中的數字在[1，1000000000]之間）

輸入數組長度n；選出的兩數字最大內插補點k；和一個長度為n的數組。

輸出最多能夠選出的數字個數。

示例1

輸入：

5

[13,4,6,9,20]

輸出：

3

解題方法：排序後周遊

很多同學在思考這道題的過程中，碰到最大的難點就是，一個數字可能同時屬于多個分組，而這個分組的大小，可能是從2~n任何一個數字。這樣的組合方式，如果用暴力的方法，挨個周遊的話，是非常恐怖的。

比如，如果這道題提供了一個長100的數組用例，那麼選出一組數可能的組合方式，就有2^100 ≈ 1024^10 ≈ 10^30種。

是以我們發現，拖累解題過程最直接的點，在于題目給的資料結構不合理。對一個無序的，可能很長的數組，怎麼可能短時間内周遊所有的“取一組數”的可能性呢？

于是，我們可以考慮，如何優化這道題提供的資料。對數組，在不違反題目要求的情況下，最簡單的優化方式就是排序。排序的時間複雜度很低，好的排序算法的空間複雜度為常數級，對本題影響很小。是以不妨假設對于一組有序的數字，再去考慮這道題，會不會發現簡單了不少？

當面對一組數字時，他們中最大的值和最小的值的內插補點如果不超過k，那麼其中任何兩個數字的內插補點，都一定不超過k。而有序數組，恰恰可以幫我們快速找到任何一組數字中的最大的值和最小的值，我們可以用一對指針，用右指針指向的值，與左指針指向的值做差，進而一次性判斷左右指針之間的值組成的一組數，是否滿足上面的條件。

當右指針與左指針的內插補點超過k時，我們可以嘗試移動左指針，重新滿足上面的條件。

當右指針與左指針的內插補點不超過k時，我們可以嘗試移動右指針，尋找所求值的最大值。

試着應用上面的思想，最佳方案應該可以達到：最壞情況下兩個指針各周遊一次數組，就可以得到正确答案了。

時間複雜度：O(nlogn)

看完是不是有了新思路了呢，快來試一下吧：

檢視題目：132.最優分組

。

上一篇： 筆試算法模拟題精解之“Bob的花束” 下一篇： 筆試算法模拟題精解之“超車”