Java non-recursive, reuse Next Permutation


  • 0
    Z
    public List<List<Integer>> permuteUnique(int[] nums) {
    		List<List<Integer>> res = new ArrayList<List<Integer>>();
            Arrays.sort(nums);
            int times = 1;
            int duplicate = 1;
            for (int i = 1; i < nums.length; i++) {
            	times *= (i + 1);
            	if (nums[i] == nums[i - 1]) {
            		duplicate++;
            	} else {
            		while (duplicate > 1) {
            			times /= duplicate;
            			duplicate--;
            		}
            		duplicate = 1;
            	}
            }
            while (duplicate > 1) {
    			times /= duplicate;
    			duplicate--;
    		}
         //if you have better way to calculate the times, please tell me
            for (int i = 0; i < times; i++) {
            	nextPermutation(nums);
            	List<Integer> temp = new ArrayList<Integer>();
            	for (int num : nums) {
            		temp.add(num);
            	}
            	res.add(temp);
            }
            return res;
        }
    	
    	public void nextPermutation(int [] nums) {
    		int indexLastAsc = -1;
    		//find the last ascend A,B
    		for (int i = nums.length - 1; i > 0; i--) {
    			if (nums[i] > nums[i - 1]) {
    				indexLastAsc = i - 1;
    				break;
    			}
    		}
    		if (indexLastAsc < 0) {//in this case, the num is biggest, we reverse it get smallest
    			for (int i = 0; i < nums.length / 2; i++) {
    				int t = nums[i];
    				nums[i] = nums[nums.length - 1 - i];
    				nums[nums.length - 1 - i] = t;
    			}
    			return;
    		}
    		
    		// 
    		for (int i = nums.length - 1; i > indexLastAsc; i--) {
    			if (nums[i] > nums[indexLastAsc]) {
    				int temp = nums[indexLastAsc];
    				nums[indexLastAsc] = nums[i];
    				nums[i] = temp;
    				break;
    			}
    		} 
    		
    		//reverse indexLastAsc to end
    		int time = (nums.length - indexLastAsc - 1) / 2;
    		for (int i = 0; i < time; i++) {
    			int t = nums[indexLastAsc + 1 + i];
    			nums[indexLastAsc + 1 + i] = nums[nums.length - 1 - i];
    			nums[nums.length - 1 - i] = t;
    		}
    	}
    		
    

Log in to reply
 

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