前往
大廳
主題

LeetCode - 0870. Advantage Shuffle 解題心得

Not In My Back Yard | 2023-12-04 12:00:23 | 巴幣 100 | 人氣 120

題目連結:


題目意譯:
你被給定兩整數陣列 nums1 和 nums2,兩者長度相同。nums1 相對於 nums2 的「優勢」為索引值 i 之數量,其中 nums1[i] > nums2[i]。

回傳任何一個 nums1 的排列,使得該排列可以最大化其相對於 nums2 的優勢。

限制:
1 ≦ nums1.length ≦ 10 ^ 5
nums2.length == nums1.length
0 ≦ nums1[i], nums2[i] ≦ 10 ^ 9



範例測資:
範例 1:
輸入: nums1 = [2,7,11,15], nums2 = [1,10,4,11]
輸出: [2,11,7,15]

範例 2:
輸入: nums1 = [12,24,8,32], nums2 = [13,25,32,11]
輸出: [24,32,8,12]


解題思維:
為了最大化 nums1 的優勢,因此我們需要用 nums1 中盡可能小的數字來使得其大於 nums2 中最小的數字、 nums1 中剩下的數字中盡可能小的數字來使得其大於 nums2 中次小的數字……以此類推。

因此我們可以將 nums1 和 nums2 按照元素大小各自排序(但記得保留原先的索引值,因為所求是 nums1 的一種排列)。

所以接著就可以用兩個指標 P1 、 P2 來指向現在分別看到的 nums1 和 nums2 之元素(P1 指到的元素以下會直接稱呼為 n1;P2 同理,其以 n2 代稱)。然後重複以下步驟直到有某個指標指到對應陣列之結尾為止:
    如果 n1 > n2,則代表優勢值會 + 1,而我們需要記錄 n1 要放到與 n2 對應的位置(也就是說,原本索引值分別為 i1 和 i2 的話,我們要記錄 nums1 的位置 i1 的數字要放到位置 i2)。此時因為兩者已經「配對完」了,因此 P1 和 P2 要指向各自的「下一個」元素;

    如果 n1 ≦ n1,則代表我們需要在 nums1 中找到更大的值來壓過 n2,因此 P1 要指向「下一個」元素。

最後根據過程中記錄的位置配對去交換 nums1 中的元素即是所求排列。




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

創作回應

更多創作