加米，求帮忙看篮子王LC46的IndexOutOfBoundException

菊二二二二 发表于 2019-12-8 03:47
同上，等于说把倒数第二个删掉了

谢谢，现在明白了！

dreamy 发表于 2019-12-7 08:40
13 和 14 换一下？ 要删的是加进去的那个最后的元素

谢谢，现在明白了！

337845818 发表于 2019-12-8 01:31
clist 为空时， 考虑一下

谢谢，现在明白了！

WarriorZ 发表于 2019-12-8 05:34
求permutation还有比N!更优的解法吗？能给个链接看一下吗？

hi，我的理解来看，这个解法时间复杂度不是n!,而是O(n * n!)。

leetcode里给出的solution提供了这个解法：

1. class Solution {
   
2.   public void backtrack(int n,
   
3.                         ArrayList<Integer> nums,
   
4.                         List<List<Integer>> output,
   
5.                         int first) {
   
6.     // if all integers are used up
   
7.     if (first == n)
   
8.       output.add(new ArrayList<Integer>(nums));
   
9.     for (int i = first; i < n; i++) {
   
10.       // place i-th integer first
    
11.       // in the current permutation
    
12.       Collections.swap(nums, first, i);
    
13.       // use next integers to complete the permutations
    
14.       backtrack(n, nums, output, first + 1);
    
15.       // backtrack
    
16.       Collections.swap(nums, first, i);
    
17.     }
    
18.   }
    
19. 
    
20.   public List<List<Integer>> permute(int[] nums) {
    
21.     // init output list
    
22.     List<List<Integer>> output = new LinkedList();
    
23. 
    
24.     // convert nums into list since the output is a list of lists
    
25.     ArrayList<Integer> nums_lst = new ArrayList<Integer>();
    
26.     for (int num : nums)
    
27.       nums_lst.add(num);
    
28. 
    
29.     int n = nums.length;
    
30.     backtrack(n, nums_lst, output, 0);
    
31.     return output;
    
32.   }
    
33. }

复制代码

这个时间复杂度大于n！，小于n*n!，可以去leetcode看一下哈

超人96825 发表于 2019-12-9 01:45
hi，我的理解来看，这个解法时间复杂度不是n!,而是O(n * n!)。

leetcode里给出的solution提供了这个 ...

又学到了，你贴的代码应该是略优于之前那个算法的，但是时间复杂度我谨慎的质疑一下，每次生成一个新的结果的时候需要把原先的list复制到答案里面去，这一步的时间复杂度是O（n）的，一共有n!个答案，所以总的时间复杂度都是O(n*n!)。后面这个算法的系数可能小一点。

哎呀，不好意思，录题时候没太注意代码的部分，下面小伙伴说的对，感谢大家指出啊