Leetcode 455 分发饼干 以有序为前提的剪枝

JAVA 剪枝前：

public final int findContentChildren(int[] g, int[] s) {
        if (s.length == 0 || g.length == 0) {
            return 0;
        }
        Arrays.sort(s);
        int re = 0;
        int sMax = s[s.length - 1];
        for (int i = 0; i < g.length; i++) {
            if (g[i] > sMax) {
                continue;
            }
            for (int j = 0; j < s.length; j++) {
                if (s[j] < g[i]) {
                    continue;
                }
                s[j] = -1;
                re++;
                break;
            }
        }
        return re;
    }

JAVA 剪枝后：

public final int findContentChildren(int[] g, int[] s) {
        if (s.length == 0 || g.length == 0) {
            return 0;
        }
        Arrays.sort(s);
        Arrays.sort(g);
        int sPoint = 0;
        int re = 0;
        int sMax = s[s.length - 1];
        for (int i = 0; i < g.length; i++) {
            if (g[i] > sMax) {
                break;
            }
            for (int j = sPoint; j < s.length; j++) {
                if (s[j] >= g[i]) {
                    sPoint = j+1;
                    s[j] = -1;
                    re++;
                    break;
                }
            }
        }
        return re;
    }

 

　　JS 剪枝后：

var findContentChildren = function (g, s) {
    if (g.length == 0 || s.length == 0) {
        return 0;
    }
    let f = (a,b)=>{return a-b;}
    g.sort(f);
    s.sort(f);
    let re = 0;
    let sPoint = 0;
    let sMax = s[s.length - 1];
    for (let i = 0; i < g.length; i++) {
        if (g[i] > sMax) {
            break;
        }
        for (let j = sPoint; j < s.length; j++) {
            if (s[j] >= g[i]) {
                sPoint = j + 1;
                re++;
                break;
            }
        }
    }
    return re;
};