ETH官方钱包

前往
大廳
主題

LeetCode - 2513. Minimize the Maximum of Two Arrays 解題心得

Not In My Back Yard | 2023-11-12 15:20:13 | 巴幣 0 | 人氣 112

題目連結:


題目意譯:
我們有兩陣列 arr1 和 arr2,其中兩者一開始都是空的。你需要新增一些正整數(shù)到這兩個陣列使得以下條件全數(shù)成真:
arr1 包含 uniqueCnt1 個相異正整數(shù),其中每個整數(shù)都不被 divisor1 整除。
arr2 包含 uniqueCnt2 個相異正整數(shù),其中每個整數(shù)都不被 divisor2 整除。
沒有整數(shù)同時出現(xiàn)於 arr1 和 arr2 中。

給定 divisor1 、 divisor2 、 uniqueCnt1 和 uniqueCnt2,回傳在兩個陣列中最小可以出現(xiàn)的最大整數(shù)。

限制:
2 ≦ divisor1, divisor2 ≦ 10 ^ 5
1 ≦ uniqueCnt1, uniqueCnt2 < 10 ^ 9
2 ≦ uniqueCnt1 + uniqueCnt2 ≦ 10 ^ 9



範例測資:
範例 1:
輸入: divisor1 = 2, divisor2 = 7, uniqueCnt1 = 1, uniqueCnt2 = 3
輸出: 4
解釋:
我們可以將前 4 個自然數(shù)到 arr1 和 arr2 中。
(譯者注:自然數(shù)在資訊科學等領域時常包含 0,所以這邊其實不恰當。改寫成非負整數(shù)就沒問題了。)
arr1 = [1] 且 arr2 = [2,3,4]。
我們可以看到兩個陣列都滿足所有條件。
因為最大值為 4,因此將其回傳。

範例 2:
輸入: divisor1 = 3, divisor2 = 5, uniqueCnt1 = 2, uniqueCnt2 = 1
輸出: 3
解釋:
這邊 arr1 = [1,2] 且 arr2 = [3] 便可以滿足所有條件。
因為最大值為 3,因此將其回傳。

範例 3:
輸入: divisor1 = 2, divisor2 = 4, uniqueCnt1 = 8, uniqueCnt2 = 2
輸出: 15
解釋:
在此,最終的可能陣列可以是 arr1 = [1,3,5,7,9,11,13,15] 且 arr2 = [2,6]。
可以證明不可能得到一個更小的最大值並滿足所有條件。


解題思維:
對答案本身進行二分搜尋法(Binary Search)即可,如這題

假設現(xiàn)在我們猜兩個陣列中的數(shù)字都不超過 M,那要怎麼檢查現(xiàn)在猜得太大還太小?可以看到我們能先檢查最基本的條件:
    - 令 C1 = M - floor(M ÷ divisor1) 、 C2 = M - floor(M ÷ divisor2),其中 floor() 對於下高斯函數(shù)。

    - 可看到 C1 、 C2 代表著各自去掉 divisor1 和 divisor2 的倍數(shù)後 nums1 和 nums2 的候選數(shù)字(先別管同時出現(xiàn)在兩者之間的)。而如果 C1 < uniqueCnt1 或是 C2 < uniqueCnt2 則表示我們猜得太小了(數(shù)字根本不夠用)。
可以看到我們還沒考慮可以同時出現(xiàn)於兩個陣列的數(shù)字,因此可以從此著手:
    - 接著再令 C = M - floor(M ÷ L),其中 L 為 divisor1 和 divisor2 的最小公倍數(shù)(Least Common Multiple)。

    - 此時可看到 C 值代表著不被 divisor1 或 divisor2 整除的那些數(shù)字之數(shù)量,也就代表著這裡面包含著可能同時出現(xiàn)於兩陣列之中的數(shù)字。而如果 C < uniqueCnt1 + uniqueCnt2,則代表數(shù)字又不夠用了(代表把只能用在單一陣列的數(shù)字分配完之後去用剩下的、可以出現(xiàn)於兩陣列中的數(shù)字後也不夠)。

因此只要過程中出現(xiàn)「數(shù)字不夠用」(根據上面的條件),就「猜大一點」;反之,我們可以試著「猜小一點」。基本上流程就跟一般二分搜尋法(Binary Search)一致了。




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

創(chuàng)作回應

更多創(chuàng)作