前往
大廳
主題

LeetCode - 2602. Minimum Operations to Make All Array Elements Equal 解題心得

Not In My Back Yard | 2024-05-28 12:00:13 | 巴幣 0 | 人氣 29

題目連結:


題目意譯:
你被給定一個由正整數所組成的陣列 nums。

你同時也被給定另一個大小為 m 的整數詢問陣列 queries。對於第 i 筆詢問,你想要讓 nums[i] 中的元素都等於 queries[i]。你可以在 nums 中執行以下操作任意次:
    把陣列中一個元素值加上或減去 1。

回傳一個大小為 m 的陣列 answer,其中 answer[i] 為讓 nums 中的數字等於 queries[i] 所需的最少操作數。

注意到在每一筆詢問之後,陣列會恢復原狀。

限制:
n == nums.length
m == queries.length
1 ≦ n, m ≦ 10 ^ 5
1 ≦ nums[i], queries[i] ≦ 10 ^ 9



範例測資:
範例 1:
輸入: nums = [3,1,6,8], queries = [1,5]
輸出: [14,10]
解釋: 對於第一筆詢問我們可以做以下操作:
- 將 nums[0] 減一 2 次,所以 nums = [1,1,6,8]。
- 將 nums[2] 減一 5 次,所以 nums = [1,1,1,8]。
- 將 nums[3] 減一 7 次,所以 nums = [1,1,1,1]。
第一筆詢問的操作總數為 2 + 5 + 7 = 14。
對於第二筆詢問我們可以做以下操作:
- 將 nums[0] 加一 2 次,所以 nums = [5,1,6,8]。
- 將 nums[1] 加一 4 次,所以 nums = [5,5,6,8]。
- 將 nums[2] 減一 1 次,所以 nums = [5,5,5,8]。
- 將 nums[3] 減一 3 次,所以 nums = [5,5,5,5]。
第二筆詢問的操作總數為 2 + 4 + 1 + 3 = 10。

範例 2:
輸入: nums = [2,9,6,3], queries = [10]
輸出: [20]
解釋: 我們可以把陣列中每一個數字增加到 10。操作總數為 8 + 1 + 4 + 7 = 20。


解題思維:
(令 n = nums.length)
首先我們觀察單一一個詢問值 queries[i]:
    可以看到各個元素之間最少所需操作數是彼此獨立的(因為一次操作只能改變一個元素值)。因此只要求出每個元素各自的最少所需操作數加總後即是此詢問的所求。

    而對於單一一個元素值 nums[i],可以看到最少操作數即為 |nums[i] - queries[i]|。也就是說差多少就補多少,數值上上下下的只是浪費時間。

    根據絕對值的定義,當 nums[i] ≧ queries[i] 時其值為 nums[i] - queries[i];反之,其值為 queries[i] - nums[i]。

    因此如果我們將 nums 中的元素由小排到大,則會存在以下三種情況:
        (一)nums 中所有數字都比 queries[i] 小。

        (二)nums 中所有數字都比 queries[i] 大。

        (三)存在某個 nums[j],滿足 nums[0] 、 nums[1] 、 …… 、 nums[j - 1] 都小於 queries[i];且 nums[j] 、 nums[j + 1] 、 …… 、nums[n - 1] 都大於等於 queries[i]。

    可以看到根據(三)的寫法會包含(二)的情況,而(一)可以藉由在「排序後」的 nums 尾巴加一個足夠大的元素便可以變成(三)之情況。

    因此我們可以找到這個 nums[j],然後算出 (queries[i] - nums[0]) + (queries[i] - nums[1]) + …… + (queries[i] - nums[j - 1]) + (nums[j] - queries[i]) + (nums[j + 1] - queries[i]) + …… + (nums[n - 1] - queries[i]) 即是對於 queries[i] 來說的最少所需操作數。

假設對於 queries[i] 滿足(三)的這個 nums[j] 之索引值為 X[i]。則我們可以看到如果有另一筆詢問 queries[i'] 滿足 queries[i] < queries[i'],則可以看到 X[i] ≦ X[i']。

而我們可以看到如果我們本來就知道「排序後的」 L[i] = nums[0] + nums[1] + …… + nums[X[i] - 1] 之值,則 L[i'] 之值只要多加上 nums[X[i]] ~ nums[X[i'] - 1] 之間的數字即可。

而一旦知道 L[i] 便可以算得 queries[i] 的最少所需操作數,其即為
((X[i] × queries[i]) - L[i]) + ((T - L[i]) - queries[i] × (n - X[i]))
當然(一)、(二)的情況理論上可以被(三)處理掉,但實際上會跟實作細節有關,所以可能要特別處理。



由上面的討論我們看到可以先將 queries 中的數字由小排到大(當然原本的索引值要保留,因為 answer[i] 求得是原本的 queries[i] 的結果)。然後先直接求排序後 queries[0] 的 X[0] 然後依序推得 X[1] 、 X[2] 等等。

而可以看到 X[i] 隨著 queries[i] 之值變大(因為已經排序了)也只會變大。因此最多只會從 nums[0] 跑到 nums[n - 1]。故此部份求 X[i] 在考慮進所有詢問之後的時間複雜度是 O(n)。

當然,前提是我們要排序 nums 以及 queries。因此總體時間複雜度 O(n log n)。




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

創作回應

更多創作