前往
大廳
主題

LeetCode - 1887. Reduction Operations to Make the Array Elements Equal 解題心得

Not In My Back Yard | 2021-09-21 00:00:07 | 巴幣 0 | 人氣 154

題目連結:


題目意譯:
給定一整數陣列 nums ,你的目標是讓 nums 中的元素全數相等。為了完成一次的操作,遵循以下步驟:
找到 nums 中最大值。令其索引值為 i (從 0 開始數)且其值為 largest。如果有多個元素為最大值,則挑最小的 i。
找到 nums 中下一個最大值(第二大)嚴格小於最大值。令其值為 nextLargest。
將 nums[i] 之值降低為 nextLargest。


回傳使 nums 中所有元素相等的操作數。

限制:
1 ≦ nums.length ≦ 5 × 10 ^ 4
1 ≦ nums[i] ≦ 5 × 10 ^ 4



範例測資:
範例 1:
輸入: nums = [5,1,3]
輸出: 3
解釋: 它將花費 3 次操作來使 nums 全部的元素相等:
1. largest = 5 於索引值 0。nextLargest = 3。將 nums[0] 降低為 3。nums = [3,1,3]。
2. largest = 3 於索引值 0。nextLargest = 1。將 nums[0] 降低為 1。nums = [1,1,3]。
3. largest = 3 於索引值 2。nextLargest = 1。將 nums[2] 降低為 1。nums = [1,1,1]。

範例 2:
輸入: nums = [1,1,1]
輸出: 0
解釋: nums 中的元素已全數相等。

範例 3:
輸入: nums = [1,1,2,2,3]
輸出: 4
解釋: 它將花費 4 次操作來使 nums 全部的元素相等:
1. largest = 3 於索引值 4。nextLargest = 2。將 nums[4] 降低為 2。nums = [1,1,2,2,2]。
2. largest = 2 於索引值 2。nextLargest = 1。將 nums[2] 降低為 1。nums = [1,1,1,2,2]。
3. largest = 2 於索引值 3。nextLargest = 1。將 nums[3] 降低為 1。nums = [1,1,1,1,2]。
4. largest = 2 於索引值 4。nextLargest = 1。將 nums[4] 降低為 1。nums = [1,1,1,1,1]。


解題思維:
將 nums 中的數字由大排到小,因此現在 nums[0] 為最大值、nums[1] 為次大值(如果 nums[0] ≠ nums[1] 的話)……以此類推。

因此,對於某個數字 nums[i] 其左的所有元素(nums[0] ~ nums[i - 1])都會各執行一次操作讓左側元素皆成為 nums[i] 之值。例如 nums = [7,5,3,1]
對於 5 而言,其左側(數字 7)會變為 5。總次數 = 1。nums = [5,5,3,1];
對於 3 而言,其左側(數字 5、5)都會變為 3。總次數 = 3。nums = [3,3,3,1];
對於 1 而言,其左側(數字 3、3、3)都會變為 1。總次數 = 6。nums = [1,1,1,1]。
此時陣列元素皆相同,因此總次數為 6 。

對於其他測資也是同理。所以我們可以掃過排序後的 nums,當 nums[i] ≠ nums[i - 1] 時,代表 nums[i] 即為下一個最大值 nextLargest。因此總次數將加上 i 次。

因此掃完之後的次數總和即為所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作