870. 優勢洗牌 :「資料結構運用」&「排序 + 雙指針」

題目描述

這是 LeetCode 上的 ​​870. 優勢洗牌​​ ，難度為 中等。

Tag : 「紅黑樹」、「哈希表」、「排序」、「雙指針」、「貪心」

給定兩個大小相等的數組 ​

​nums1​

​​ 和 ​

​nums2​

​​，​

​nums1​

​​ 相對于 ​

​nums​

​​ 的優勢可以用滿足 ​

​nums1[i] > nums2[i]​

​​ 的索引 ​

​i​

​ 的數目來描述。

傳回 ​

​nums1​

​​ 的任意排列，使其相對于 ​

​nums2​

​ 的優勢最大化。

示例 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]      

提示：

資料結構

顯然，對于任意一個 而言，我們應當在候選集合中選擇比其大的最小數，若不存在這樣的數字，則選擇候選集合中的最小值。

同時，由于

也就是我們總共涉及兩類操作：

1. 實時維護一個候選集合，該集合支援高效查詢比某個數大的數值操作；
2. 對候選集合中每個數值的可使用次數進行記錄，當使用到了候選集合中的某個數後，要對其進行計數減一操作，若計數為，則将該數值從候選集合中移除。

計數操作容易想到哈希表，而實時維護候選集合并高效查詢可以使用基于紅黑樹的 ​

​TreeSet​

​ 資料結構。

Java 代碼：

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;
        TreeSet<Integer> tset = new TreeSet<>();
        Map<Integer, Integer> map = new HashMap<>();
        for (int x : nums1) {
            map.put(x, map.getOrDefault(x, 0) + 1);
            if (map.get(x) == 1) tset.add(x);
        }
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            Integer cur = tset.ceiling(nums2[i] + 1);
            if (cur == null) cur = tset.ceiling(-1);
            ans[i] = cur;
            map.put(cur, map.get(cur) - 1);
            if (map.get(cur) == 0) tset.remove(cur);
        }
        return      

Python 代碼：

from sortedcontainers import SortedList

class Solution:
    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
        n = len(nums1)
        cnts, tset = defaultdict(int), SortedList()
        for i in range(n):
            cnts[nums1[i]] += 1
            if cnts[nums1[i]] == 1:
                tset.add(nums1[i])
        ans = [0] * n
        for i in range(n):
            t = nums2[i]
            if (idx := tset.bisect_left(t + 1)) == len(tset):
                idx = tset.bisect_left(-1)
            ans[i] = tset[idx]
            cnts[ans[i]] -= 1
            if cnts[ans[i]] == 0:
                tset.remove(ans[i])
        return      

• 時間複雜度：
• 空間複雜度：

排序 + 雙指針

在解法一中，我們是從每個 出發考慮，使用哪個

實際上，我們也能從 出發，考慮将其與哪個

為了讓每個決策回合具有獨立性，我們需要對兩數組進行排序，同時為了在構造答案時，能夠對應回 ​

​nums2​

​​ 的原下标，排序前我們需要使用「哈希表」記錄每個

使用變量 ​

​l1​

​​ 代表目前決策将 配置設定到哪個 ​​

​nums2​

​​ 的位置，使用 ​

​l2​

​​ 和 ​

​r2​

​​ 代表目前 ​

​nums2​

​​ 中還有

可以證明我們在從前往後給每個 配置設定具體位置時，配置設定的位置隻會在 ​​

​l2​

​​ 和 ​

​r2​

​ 兩者之間産生。

Java 代碼：

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            List<Integer> list = map.getOrDefault(nums2[i], new ArrayList<>());
            list.add(i);
            map.put(nums2[i], list);
        }
        Arrays.sort(nums1); Arrays.sort(nums2);
        int[] ans = new int[n];
        for (int l1 = 0, l2 = 0, r2 = n - 1; l1 < n; l1++) {
            int t = nums1[l1] > nums2[l2] ? l2 : r2;
            List<Integer> list = map.get(nums2[t]);
            int idx = list.remove(list.size() - 1);
            ans[idx] = nums1[l1];
            if (t == l2) l2++;
            else r2--;
        }
        return      

Python 代碼：

class Solution:
    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
        n = len(nums1)
        mapping = defaultdict(list)
        for i in range(n):
            mapping[nums2[i]].append(i)
        nums1.sort()
        nums2.sort()
        ans = [0] * n
        l2, r2 = 0, n - 1
        for l1 in range(n):
            t = l2 if nums1[l1] > nums2[l2] else r2
            ans[mapping[nums2[t]].pop()] = nums1[l1]
            if t == l2:
                l2 += 1
            else:
                r2 -= 1
        return      

• 時間複雜度：
• 空間複雜度：

加餐

加餐一道同類型題目 : ​​難度 2.5/5，敲醒沉睡心靈的資料結構運用題​​ 🎉🎉

最後

這是我們「刷穿 LeetCode」系列文章的第 ​

​No.870​

​ 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。

在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。