java - 匹配的盖子和罐子实施

Question

此处描述了该问题，实现将盖子与正确大小的罐子匹配的算法。

这是我的实现

public class MyMatcher implements Matcher {

private List<Pair> res = new ArrayList<>();

@Override
public List<Pair> match(List<Jar> jars, List<Lid> lids) {
    int n = jars.size()-1;
    List<Jar> jsorted = quickSortPivotLid(jars,lids,0,n);
    List<Lid> lsorted = quickSortPivotJar(jars,lids,0,n);
    for(int i=0; i<=n; i++){
        res.add(new Pair(jsorted.get(i),lsorted.get(i)));
    }
    return res;
}

private List<Jar> quickSortPivotLid(List<Jar> jars, List<Lid> lids, int left, int right){
    if(left>=right){
        return jars;
    }
    int pi = partitionPivotLid(jars,lids,left,right);
    quickSortPivotLid(jars,lids,left,pi);
    quickSortPivotLid(jars,lids,pi+1,right);
    return jars;
}
private int partitionPivotLid(List<Jar> jars, List<Lid> lids, int left, int right){
    List<Jar> copy = new ArrayList<Jar>();
    for(Jar jar: jars){
        copy.add(jar);
    }
    Lid pivot = lids.get(left);
    int ind = -1; //index of jar that corresponds to pivotal lid;
    int l = left;
    while(copy.get(l).compareTo(pivot)!=0) {
        l++;
    }
    if(copy.get(l).compareTo(pivot)==0){
        ind = l;
    }
    Collections.swap(copy,ind,left);
    int i = left;
    for(int j=left+1; j<=right; j++){
        if(copy.get(j).compareTo(spil)<=0){ 
            i++;
            Collections.swap(copy,i,j);
        }
    }
    Collections.swap(copy,left,i);
    return i; 
}

private List<Lid> quickSortPivotJar(List<Jar> jars, List<Lid> lids, int left, int right){
    if(left>=right){
        return lids;
    }
    int pi = partitionPivotJar(jars,lids,left,right);
    quickSortPivotLid(jars,lids,left,pi);
    quickSortPivotLid(jars,lids,pi+1,right);
    return lids;
}
private int partitionPivotJar(List<Jar> jars, List<Lid> lids, int left, int right){
    List<Lid> copy = new ArrayList<Lid>();
    for(Lid lid: lids){
        copy.add(lid);
    }
    Jar pivot = jars.get(left);
    int ind = -1; 
    int l = left;
    while(copy.get(l).compareTo(pivot)!=0) {
        l++;
    }
    if(copy.get(l).compareTo(pivot)==0){
        ind = l;
    }
    Collections.swap(copy,ind,left); 
    int i = left;
    for(int j=left+1; j<=right; j++){
        if(copy.get(j).compareTo(pivot)<=0){
            i++;
            Collections.swap(copy,i,j);
        }
    }
    Collections.swap(copy,left,i);
    return i; 
}

}

注意：QuickSortPivotLid 使用一个枢轴盖，partitionPivotLid 使用这个枢轴盖对罐子列表进行分区。

这段代码看起来像是一个合理的解决方案吗？可以缩短吗？

谢谢。

标签： javaalgorithmmatch