主題
題目連結(jié)：
題目意譯：
一個元素的頻率定義為其在一陣列之中的出現(xiàn)次數(shù)。
你被給定一整數(shù)陣列 nums 以及一整數(shù) k。在一次操作中，你可以選擇 nums 中的一個索引值並將位於該索引值的元素之值加 1。
回傳執(zhí)行最多 k 次操作之後，一個元素最大可能的頻率為何。
限制：
1 ≦ nums.length ≦ 10 ^ 5
1 ≦ nums[i] ≦ 10 ^ 5
1 ≦ k ≦ 10 ^ 5
範例測資：
範例 1：
輸入： nums = [1,2,4], k = 5
輸出： 3
解釋： 將第一個元素增加三次並將第二個元素增加兩次，使得 nums 變?yōu)?[4,4,4]。
4 有著頻率值 3。
範例 2：
輸入： nums = [1,4,8,13], k = 5
輸出： 2
解釋： 有多組最佳解：
- 將第一個元素增加三次，使得 nums 變?yōu)?[4,4,8,13]。4 有著頻率值 2。
- 將第二個元素增加四次，使得 nums 變?yōu)?[1,8,8,13]。8 有著頻率值 2。
- 將第三個元素增加五次，使得 nums 變?yōu)?[1,4,13,13]。13 有著頻率值 2。
範例 3：
輸入： nums = [3,9,6], k = 2
輸出： 1
解題思維：
假設現(xiàn)在我們知道某數(shù) nums[i] 在經(jīng)由 C 次操作（當然，C ≦ k）後會變成頻率最大的，其頻率值為 F。
已知題目定義的操作只能把數(shù)字變大，因此在原始陣列中找出最靠近且小於等於 nums[i] 的 F - 1 個數(shù)字，將它們的值統(tǒng)一變成 nums[i]。這樣子的操作數(shù)必定不會超過 C 次。換句話說，必定存在一組最佳解是經(jīng)由前述方式來得到 F 次的 nums[i]（前提是我們知道 nums[i] 要出現(xiàn) F 次）。
而如果我們把 nums 中的數(shù)字由小排到大，則最靠近且小於等於 nums[i] 的 F - 1 個數(shù)字就是排在排序後的 nums[i] 左邊的 F - 1 個數(shù)字（如果有多個數(shù)字等於 nums[i]，則取最右邊的 nums[i] 之位置即可）。
現(xiàn)在我們便可以對答案（即頻率）本身進行二分搜尋法（Binary Search）。因為如果最大可行頻率為 F，則 F + 1 、 F + 2 、…… 是不可能的，而 F - 1 、 F - 2 、…… 則都同樣可行但不是最大。
假設現(xiàn)在我們猜了頻率值 f。要檢查其可不可行需要排序後的 nums 之前綴和（Prefix Sums）或是利用滑動視窗（Sliding Window）的技巧來進行。而因為我們範例程式碼是使用滑動視窗，因此以下使用此技巧來說明：
首先假設我們猜最佳解是發(fā)生在 nums[f - 1] 身上（不可能發(fā)生在 nums[0] ～ nums[f - 2] 上，因為數(shù)字不足 f 個），然後用一個迴圈計算出每個 nums[i]（0 ≦ i < f - 1）與 nums[f - 1] 差多少。將這些差值加總得一值 X，此時這個 X 即為將 nums 中的 f - 1 個數(shù)字變成 nums[f - 1] 最少所需操作數(shù)（根據(jù)一開始的敘述）。
此時如果我們改猜最佳解發(fā)生在 nums[f] 上，其對應的 X 值不用按照上面的過程重新求一次。我們比較一下兩者的 X 值（為了方便把 nums[f - 1] 和 nums[f] 本身也納入 X 值的計算之中，實際上不影響結(jié)果）：
nums[f - 1] 的：nums[0] ～ nums[f - 1] 變成 nums[f - 1]；
nums[f] 的：nums[1] ～ nums[f] 變成 nums[f]。
兩者的實際差異只有 nums[0] 要從 nums[f - 1] 變回原本的數(shù)值，而 nums[1] ～ nums[f - 1] 要從 nums[f - 1] 變成 nums[f]。
因此已知 nums[f - 1] 的 X 時，只需要減去 (nums[f - 1] - nums[0]) 並加上 (nums[f] - nums[f - 1]) × (f - 1) 後便可以得到 nums[f] 的 X 值。
更一般地來說，當我們已知 nums[i - 1] 的 X 值且要將焦點轉(zhuǎn)移到 nums[i] 時，只需要將 X 減去 (nums[i - 1] - nums[i - f]) 並加上 (nums[i] - nums[i - 1]) × (f - 1) 即可。
而掃完一次 nums 之後，如果發(fā)現(xiàn)有人的 X 值是 ≦ k 的，則代表現(xiàn)在猜的頻率值 f 是可行的。因此可以試著猜更大的頻率值；反之，則代表我們猜得太大了，要猜小一點才對。
最後便可以得到一個可行且最大的頻率值 F，即為所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
