1887. Reduction Operations to Make the Array Elements Equal
給你一個陣列
你要把所有元素變成相等
你只能做一種操作，操作步驟如下：
1.找到最大的數的其中一個
2.找到比除了最大數以外的次大的數
3.將剛才找到的數變成次大的數
求把所有元素便相等需要操作的次數
Input: nums = [5,1,3]
Output: 3
[5,1,3]->[3,1,3]->[1,1,3]->[1,1,1]
Input: nums = [1,1,1]
Output: 0
Input: nums = [1,1,2,2,3]
Output: 4
[1,1,2,2,3]->[1,1,2,2,2]->[1,1,1,2,2]->[1,1,1,1,2]->[1,1,1,1,1]
Intuition:
計算出出現的個數之後，累加起來。
Approach:
以[1,2,3,4]舉例
一開始我們先處裡[3,4] -> [3,3]
然後是[2,3,3] -> [2,2,2]
接下來是[1,2,2,2] -> [1,1,1,1]
從規律可以得知比1大的都要加一遍
接下來是比2大的都要加一遍
以此類推
所以我們只要一直累加起來就是答案
TS Code:
function reductionOperations (nums: number[]): number {
const counts: number[] = new Array(50001).fill(0)
for (let i = 0; i < nums.length; i++) {
counts[nums[i]]++
}
let leftAmount = nums.length
let answer = 0
for (let i = 0; i < counts.length; i++) {
if (counts[i] === 0) continue
leftAmount -= counts[i]
answer += leftAmount
}
return answer
}