基本概念

所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

贪心算法的基本思路

建立数学模型来描述问题。
把求解的问题分成若干个子问题。
对每一子问题求解，得到子问题的局部最优解。
把子问题的解局部最优解合成原来解问题的一个解。

贪心算法的实现框架

从问题的某一初始解出发；

while （能朝给定总目标前进一步）

{

利用可行的决策，求出可行解的一个解元素；

}

由所有解元素组合成问题的一个可行解；

例题:优势洗牌

给定两个大小相等的数组 A 和 B，A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。

返回 A 的任意排列，使其相对于 B 的优势最大化。

示例 1：

1 2	输入：A = [2,7,11,15], B = [1,10,4,11] 输出：[2,11,7,15]

示例 2：

1 2	输入：A = [12,24,8,32], B = [13,25,32,11] 输出：[24,32,8,12]

提示：

1
2
3

1 <= A.length = B.length <= 10000
0 <= A[i] <= 10^9
0 <= B[i] <= 10^9

解决方案:

class Solution {
    public int[] advantageCount(int[] A, int[] B) {
        Arrays.sort(A);
        List<Integer> a = new ArrayList<>();
        for (int a0 : A) {
            a.add(a0);
        }
        int[] res = new int[A.length];
        for (int i = 0, len = B.length; i < len; i++) {
            res[i] = find(a, B[i], 0, a.size() - 1);
        }
        return res;
    }

    private int find(List<Integer> a, int target, int head, int last) {
        if (a.get(last) <= target || a.get(head) > target) {
            int res = a.get(head);
            a.remove(head);
            return res;
        }
        while (a.get(head) <= target && a.get(last) > target) {
            if (last - head == 1) {
                int res = a.get(last);
                a.remove(last);
                return res;
            }
            int mid = (head + last) / 2;
            if (a.get(mid) <= target) {
                head = mid;
            } else {
                last = mid;
            }
        }
        return 0;
    }
}