Java ArrayList 克隆改进了运行时

Question

这是问题:https://leetcode.com/problems/combinations/

这是我的解决方案 1:

   public class Solution {

    public List<List<Integer>> combine(int n, int k){
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        combine(n, k, 1, result, new ArrayList<Integer>());
        return result;
    }

    public void combine(int n, int k , int start, List<List<Integer>> result, ArrayList<Integer> l){
        if(k == 0){
            result.add(l);
            return;
        }
        for(int i = start; i <= n; ++i){

            l.add(i);
            combine(n, k - 1, i + 1, result, l);
        }
    }


    }

结果:小测试用例通过。但是大的测试用例时间超过了。

提交结果:超时最后执行的输入:10、5

解决方案 2:

public class Solution {

public List<List<Integer>> combine(int n, int k){
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    combine(n, k, 1, result, new ArrayList<Integer>());
    return result;
}

public void combine(int n, int k , int start, List<List<Integer>> result, ArrayList<Integer> l){
    if(k == 0){
        result.add(l);
        return;
    }
    for(int i = start; i <= n; ++i){
        ArrayList<Integer> a = (ArrayList<Integer>) l.clone();
        a.add(i);
        combine(n, k - 1, i + 1, result, a);
    }
}


}

通过所有测试用例。

主要区别在于列表的克隆。但为什么？解决方案 A 是错误的还是速度很慢？为什么在这里使用克隆更快？真的很困惑。

Answer 1

第一个解决方案确实不正确。尝试调用 combine(5,3)，并将其发送到 System.out，您将看到第一个输出是:

[[1, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5, 2, 3, 4, 5, 4, 5, 5, 3, 4, 5, 5, 4, 5, 5], [1, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5, 2, 3, 4, 5, 4, 5, 5, 3, 4, 5, 5, 4, 5, 5], [1, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5, 2, 3, 4, 5, 4, 5, 5, 3, 4, 5, 5, 4, 5, 5], [1, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5, 2, 3, 4, 5, 4, 5, 5, 3, 4, 5, 5, 4, 5, 5], [1, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5, 2, 3, 4, 5, 4, 5, 5, 3, 4, 5, 5, 4, 5, 5], [1, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5, 2, 3, 4, 5, 4, 5, 5, 3, 4, 5, 5, 4, 5, 5], [1, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5, 2, 3, 4, 5, 4, 5, 5, 3, 4, 5, 5, 4, 5, 5], [1, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5, 2, 3, 4, 5, 4, 5, 5, 3, 4, 5, 5, 4, 5, 5], [1, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5, 2, 3, 4, 5, 4, 5, 5, 3, 4, 5, 5, 4, 5, 5], [1, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5, 2, 3, 4, 5, 4, 5, 5, 3, 4, 5, 5, 4, 5, 5]]

您会注意到它在每个索引位置都是相同的列表 - 您确实需要每次都创建一个新数组。对于第二个正确的解决方案，输出为:

[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]

这意味着第一个解决方案较慢，因为您每次都将数字添加到越来越大的列表中。对于更高的 n 和 k 值，该列表可能非常大，并且在需要扩展时复制 ArrayList 的支持数组成为非常昂贵的操作 - 比复制/创建多个小列表。