筆試算法模拟題精解之“完美排列”

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

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

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

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

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

點選連結開始産品體驗：

https://developer.aliyun.com/coding 本文為大家介紹的是“86.完美排列”的解法探究。先來看一下題目内容：

題目描述

等級：容易

知識點：貪心

檢視題目：86.完美排列

完美排列的定義為一個長度為n的數組，n個元素各不相同且每個元素均在[1,n]的範圍内。

現在給你長度為n的數組，你每次可以進行如下操作：任選數組中的一個元素，将其加一或者減一，問最少需要多少次操作才能夠使得該數組為一個完美排列。

輸入一個整數n，表示數組的長度(1 <= n <= 10^4)；

再輸入含有n個數的數組，第i個數表示數組中的第i個元素為ai（1 <= ai <= 10^5）。

輸出一個整數表示将該數組變成一個完美排列的最少操作次數。

示例1

輸入：

2

[3,0]

輸出：

注意：

3->2

0->1

總共需要操作兩次。

解法探究

解法一：正常貪心思路

本題是一道典型的貪心算法題，問題可以通過每步的最優政策分治解決。如果将 n 個大小未知的正整數，通過題目中的規則“填充”到槽 1~n 中，我們不妨從最小的數字槽 1 開始做起。

顯然，這 n 個正整數中最小的數字 a（無論這個最小的數字是 1 或是 100），是填充槽 1 的最佳選擇。其它(n-1)個數字和 1 的“距離”，都必定大于等于 a，距離槽 1 的距離都不如 a 更優，是以可以将 a 填充進槽 1，并在後續選擇中排除掉它。

當填充槽 2 時，依舊用上面的思路就可以了。用剩下的(n-1)個數字中最小的數字去通過加減 1 進入槽 2，必定是填充槽 2 所有方式中的最佳政策。

将上面的思路重複應用，就得到了結果。複雜度上需要掃描 n 次數組。

時間複雜度：O(n^2)

空間複雜度：O(1)

解法二：排序優化

上面的反複掃描非常浪費時間，不如提前對數組排序，然後從排序後遞增數組的第一項開始，逐個比較與槽 1~n 的距離，最後加到一起，得到答案。

時間複雜度：O(logn)

看完之後是不是有了答題思路了呢，快來練練手吧：

檢視題目：完美排列

線上程式設計周賽、月賽火熱進行中，更有限時答題活動，社群定制衛衣、雙肩背包等你來拿~每天都有好禮相送~點選了解周賽詳情：

線上程式設計内測中，搶先周賽赢好禮！面試考試前，快來刷刷題！

上一篇： 筆試算法模拟題精解之“壞掉的時鐘” 下一篇： 筆試算法模拟題精解之“Bob的花束”的“模拟”解法