<p>You are given two integer arrays <code>nums1</code> and <code>nums2</code> both of the same length. The <strong>advantage</strong> of <code>nums1</code> with respect to <code>nums2</code> is the number of indices <code>i</code> for which <code>nums1[i] &gt; nums2[i]</code>.</p>

<p>Return <em>any permutation of </em><code>nums1</code><em> that maximizes its <strong>advantage</strong> with respect to </em><code>nums2</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> nums1 = [2,7,11,15], nums2 = [1,10,4,11]
<strong>Output:</strong> [2,11,7,15]
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> nums1 = [12,24,8,32], nums2 = [13,25,32,11]
<strong>Output:</strong> [24,32,8,12]
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums1.length &lt;= 10<sup>5</sup></code></li>
	<li><code>nums2.length == nums1.length</code></li>
	<li><code>0 &lt;= nums1[i], nums2[i] &lt;= 10<sup>9</sup></code></li>
</ul>

'''
題目的要求是
要去對nums1作排列
盡量排出，對到同位置的nums2時，可以贏最多位置的排列方式

感覺是要盡量找到下駟對上駟
提到"盡量"就可以試著往greedy的方向來想
要是可以只贏nums2一點點，就盡量只排贏一點點的牌
大的牌留著對付更大的

那要是怎麼都贏不了，就用最小的牌去擋
用叔辣換將軍

class Solution:
    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
        heapq.heapify(nums1)
        h = nums1
        result = []
        for i in range(len(nums2)):
            nextH = []
            found = False
            while h:
                minNum = heapq.heappop(h)
                if minNum > nums2[i]:
                    result.append(minNum)
                    found = True
                    break
                else:
                    nextH.append(minNum)
            if not found:
                result.append(nextH[0])
                h = h+nextH[1:]
            else:
                h = h+nextH
            heapq.heapify(h)
        return result
===================================
class Solution:
    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        result = []
        for i in range(len(nums2)):
            if nums2[i] >= nums1[-1]:
                result.append(nums1[0])
                nums1.pop(0)
                continue
            mid = len(nums1) // 2
            if nums1[mid] > nums2[i]:
                maxPtr = mid
                while maxPtr >= 0 and nums1[maxPtr] > nums2[i]:
                    maxPtr -= 1

                result.append(nums1[maxPtr])
            else:
                minPtr = mid
                if nums1[minPtr] > nums2[i]:
                    result.append(nums1[minPtr])
                    nums1.pop(minPtr)
                    break
                minPtr += 1
        return result
寫了兩個解法都會timeout
因為想不出來，怎樣才能夠省掉
"去找到比目前只到的nums2的位置的值還要大一點的數字"
的時間
不論怎樣都要再去loop一次nums1來看看有沒有比nums2現在這個位置的值大一點
===============================================
後來偷看解答
解題的思維要變成
如果現在nums1中最大的值
可以贏過nums2中目前最大的值
那就可以排它
因為我們最大的已經可以贏過對方最大的
雖然這也代表我們的最大的
可以贏過對方的所有其他的牌
但不管贏過什麼牌，贏了也只都算一場而已

那就不用顧慮什麼了，直接派出去
就先贏一場算一場
相反的
如果在我們這邊最大的可以贏對方最大的情況下
我們還不派最大的去打
那表示我們最大的會跟對方之後比較弱的牌打
雖然是一定會贏
可是這樣就有可能變成拿大砲打小鳥
我們這邊反而要派出有可能贏不了的其他牌
去跟對方最大的打

那要是連我們最大的，都打不過對方最大的
那就表示真的贏不了，所以派個小蝦米去耗掉它的大將軍

'''
class Solution:
    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result = [0] * len(nums1)
        sorted1 = sorted(nums1)
        sorted2 = sorted( [(nums2[i], i) for i in range(len(nums2))], reverse = True)

        left = 0
        right = len(nums1) - 1
        for num, i in sorted2:
            if sorted1[right] > num:
                result[i] = sorted1[right]
                right -= 1
            else:
                result[i] = sorted1[left]
                left += 1
        return result
39282