A simple java solution beats lots of codes, 268ms


  • 0
    Q
    public void helper(int[] nums,int cur,ArrayList<Integer> list,List<List<Integer>> res){
    	
    	if(list.size()==nums.length){
    		res.add(new ArrayList<Integer>(list));
    		return;
    	}
    	
    	for(int i=cur;i<nums.length;i++){
    		for(int j=0;j<=list.size();j++){
    			list.add(j, nums[i]);
    			helper(nums,i+1,list, res);
    			list.remove(j);
    		}
    	}
    }
    
    //求nums这些数的全排列
    public List<List<Integer>> permute(int[] nums) {
    	List<List<Integer>> res = new ArrayList<List<Integer>>();
    	helper(nums, 0, new ArrayList<Integer>(), res);
    	return res;
    }

  • 2
    W

    Actually the i iteration is not necessary at all. You can replace the line

       for(int i=cur;i<nums.length;i++)
    

    by

        for(int i=cur;i<=cur;i++)
    

    and you will see the program still works well.


  • 0
    Q

    you are right, but after replacing that line, the program becomes much slower.


  • 0

    Why would that make it slower? It doesn't.


  • 0
    Q

    the time for changed code is 316 ms


  • 0

    No it's not. I just got it accepted in 252 ms and your original in 368 ms (not 268 ms). Solutions don't have a fixed time. There's huge variation.


  • 0

    Also, there are so few test cases and they're so tiny that your solution time almost doesn't matter at all. I just got it accepted in 628 ms despite doing 1000 times as much work:

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = null;
        for (int i=0; i<1000; ++i) {
            res = new ArrayList<List<Integer>>();
            helper(nums, 0, new ArrayList<Integer>(), res);
        }
        return res;
    }
    

    Assuming 252 ms as the baseline, that's (628-252)/1000 = 0.376 ms spent by the actual solution, which means 1-0.376/252 = 99.85% of the time is spent by the judge, not your solution. You have no chance of meaningfully comparing the solution speeds with this. Unless you have a really really awfully slow solution, the time and the time variation are almost purely luck and have nothing to do with your solution.


  • 0
    Q

    thanks very much, I will check it


  • 0
    M

    res.add(new ArrayList<Integer>(list));
    Here why we need to add a new ArrayList<Integer>(list), instead of just res.add(list);


  • 0
    Q

    res.add(new ArrayList(list)) means making a deep copy of list, ,res.add(list) just add the original one list


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.