AC Java Solution 78% faster no set using next permutation


  • 0
    A

    Logic:

    Sort the nums to get the first permutation.

    Keep getting the nextPermutation from the nextPermutation method until the next permutation can not return any more

    nextPermutation method will not return any more once the nums array is reverse sorted

    See // https://leetcode.com/discuss/8472/share-my-o-n-time-solution for explanations on nextPermutation logic

        public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        
        if(nums == null || nums.length == 0)
            return result;
            
        Arrays.sort(nums);
        
        //http://stackoverflow.com/questions/4792160/arrays-aslist-doubt
        // asList() doesn't return a java.util.ArrayList, it returns a java.util.Arrays$ArrayList. 
        // This class doesn't even extend java.util.ArrayList, so its behaviour can be (and is) completely different.
        
        result.add(arrayToArrayList(nums));
        
        while(nextPermutation(nums)) {
            result.add(arrayToArrayList(nums));
        }
        
        return result;
    }
    
    public boolean nextPermutation(int[] nums) {
        if(nums == null || nums.length == 0)
            return false;
            
        int len = nums.length;
        
        int i = len-2;
        
        while(i >= 0) {
            if(nums[i] < nums[i+1])
                break;
                
            i--;
        }
        
        if(i == -1)
            return false;
        
        int j = len-1;
        
        while(j > i) {
            if(nums[j] > nums[i])
                break;
            
            j--;
        }
        
        swap(nums, i, j);
        reverse(nums, i+1, len-1);
        
        return true;
    }
    
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    public void reverse(int[] nums, int start, int end) {
        while(start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }
    
    public ArrayList<Integer> arrayToArrayList(int nums[]) {
        ArrayList<Integer> arrayList =  new ArrayList<Integer>();
        
        for(int n : nums) {
            arrayList.add(n);
        }
        
        return arrayList;
    }
    }
    

    Inspiration from https://leetcode.com/discuss/38260/easy-solution-using-code-in-nextpermutation


Log in to reply
 

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