Re: [閒聊] 每日LeetCode
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
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.229.33 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1700368586.A.315.html
推
11/19 12:49,
2年前
, 1F
11/19 12:49, 1F
討論串 (同標題文章)
完整討論串 (本文為第 529 之 719 篇)：