主題
題目連結：
題目意譯：
你被給定一個索引值從 0 開始的陣列 arr 以及一整數 k。陣列 arr 是環狀的。換句話說，陣列的第一個元素為最後一個元素的「下一個」元素；而陣列的最後一個元素是第一個元素的「前一個」元素。
你可以執行以下操作任意次：
從 arr 中選擇一個元素並將其值加上或減去 1。
回傳讓 nums 中每一個長度為 k 的子陣列之元素總和都一樣，所需的最少操作數。
一個子陣列為陣列中的一個連續部份。
限制：
1 ≦ k ≦ arr.length ≦ 10 ^ 5
1 ≦ arr[i] ≦ 10 ^ 9
範例測資：
範例 1：
輸入： arr = [1,4,1,3], k = 2
輸出： 1
解釋： 我們可以在索引值 1 上做一次操作並使得其值變為 3。
執行完操作後的陣列是 [1,3,1,3]
- 從索引值 0 開始的子陣列為 [1, 3]，而其總和為 4
- 從索引值 1 開始的子陣列為 [3, 1]，而其總和為 4
- 從索引值 2 開始的子陣列為 [1, 3]，而其總和為 4
- 從索引值 3 開始的子陣列為 [3, 1]，而其總和為 4
範例 2：
輸入： arr = [2,5,5,7], k = 3
輸出： 5
解釋： 我們可以在索引值 0 上做三次操作並使其值變為 5，再做兩次在索引值 3 上使其值變為 5。
執行完操作後的陣列是 [5,5,5,5]
- 從索引值 0 開始的子陣列為 [5, 5, 5]，而其總和為 15
- 從索引值 1 開始的子陣列為 [5, 5, 5]，而其總和為 15
- 從索引值 2 開始的子陣列為 [5, 5, 5]，而其總和為 15
- 從索引值 3 開始的子陣列為 [5, 5, 5]，而其總和為 15
解題思維：
（令 n = arr.length）
因為每一個長度為 k 子陣列之總和要一樣，因此我們可以列出下列等式
arr[i] + arr[i + 1] + …… + arr[i + k - 1] = arr[i + 1] + arr[i + 2] + …… + arr[i + k]
化簡可得
arr[i] = arr[i + k]
同理，
arr[i] = arr[i + k] = arr[i + 2k] = …… = arr[i + kx]
其中 x 為一整數。
又因為 arr 實際上是一個環狀陣列，因此每往一個方向數 n 個元素便會回到原地。故
arr[i] = arr[(i + kx) % n]
而這又可寫為
arr[i] = arr[i + kx + ny]
其中 y 為一整數。而根據貝祖定理（Bézout's Identity），kx + ny 有 x 、 y 之整數解若且唯若
kx + ny = gd
其中 g 為 k 和 n 的最大公因數、 d 為任意整數。因此實際上
arr[i] = arr[i + gd]
所以我們可以把 arr 中的數字分成 g 組，其中
第一組由索引值 0 、 g 、 2g 、…… 組成；
第二組由索引值 1 、 g + 1 、 2g + 1 、…… 組成；
……
第 g 組由索引值 g - 1 、 2g - 1 、 3g - 1 、…… 組成。
而每一組 i 、 i + g 、 i + 2g 、 …… 中，我們需要讓 arr 滿足
arr[i] = arr[i + g] = arr[i + 2g] …… = X
並且操作數要盡可能地少。
而可以看到我們要找到一個 X 值滿足
|X - arr[i]| + |X - arr[i + g]| + ……
為最小值。我們可以看到這個問題即是這題。因此我們可以將 arr[i] 、 arr[i + g] 等排序後找其中的中位數（Median）即為一個符合要求的 X 值。因此單一一組的時間複雜度為 O(s × log(s))，其中 s = n ÷ g，即一組的最大數字數量。
這部份可以用快速選擇法（Quick Select）在平均時間 O(s) 做到，或甚至是用「中位數的中位數」（Median Of Medians）來加速至最糟時間為 O(s)。但排序就夠用了。不過範例程式碼中是用 C++ 中的 nth_element 來加速（基本上就是快速選擇法）。
而最後我們只要將每一組的 X 值套入
|X - arr[i]| + |X - arr[i + g]| + ……
得到各自的最少操作數，再全數加總即是整體所需最少操作數。而時間複雜度為 O(g × s × log(s)) = O(n × log(n))。
題外話：本題的正確性證明是整題最難的部份。如果連正確性證明都加進來，我相信本題應是 Hard 而非 Medium XD。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
