# 0870. Advantage Shuffle
###### tags: `Leetcode` `Medium` `Greedy`
Link: https://leetcode.com/problems/advantage-shuffle/
## 思路
### 思路一 TreeMap $O(NlogN)$ $O(N)$
先把nums1都存在TreeMap里面，然后用```higherKey()```找到比它大的最小的key 如果没有就把最小值给它
### 思路二 $O(NlogN)$ $O(N)$
第一反应是给两个array排序 (nums2需要是倒序) 然后遍历nums2 在nums1上面用双指针 先看右指针指的数字是不是比nums2现在的数字大 如果不是的话就只能用左指针指的比较小的数(也就是第9-11行做的事情)
但是这样会导致原来的顺序错了 方法就是我们**不排序数字本身 我们排序index** 这样就可以保留顺序了
不过需要注意的是排序index不能写成```Arrays.sort(index, (a,b)->(nums2[b]-nums2[a]))```而是要写成```Arrays.sort(index, (a,b)->Integer.compare(nums2[b], nums2[a])``` 同时index的数据类型还要设成Integer
## Code
### 思路一

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        TreeMap<Integer, Integer> cnt = new TreeMap<>();
        for(int num:nums1) cnt.put(num, cnt.getOrDefault(num, 0)+1);
        int[] ans = new int[nums1.length];
        
        for(int i=0; i<nums2.length; i++){
            int num = nums2[i];
            Integer next = cnt.higherKey(num);
            if(next==null) next = cnt.firstKey();
            cnt.put(next, cnt.get(next)-1);
            if(cnt.get(next)==0) cnt.remove(next);
            ans[i] = next;
        }
        return ans;
    }
}

### 思路二

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int[] ans = new int[nums1.length];
        Integer[] index = new Integer[nums1.length];
        for(int i=0; i<nums1.length; i++) index[i]=i;
        Arrays.sort(index, (a,b)->Integer.compare(nums2[b],nums2[a]));
        Arrays.sort(nums1);
        
        int l=0, r=nums1.length-1;
        for(int idx:index){
            ans[idx] = nums2[idx]<nums1[r]?nums1[r--]:nums1[l++];
        }
        return ans;
    }
}