Associate with "NextPermutation" question


  • 1
    E

    This question is highly dependent on "Next Permutation" question, so if you solved that problem, simply apply it here. Below is the accepted code.

    public class Solution {
    	private class NextPermutation {
    		private int getFirstDecrease(int[] num){
    			int n = num.length-1;
    			while(n>=1){
    				if(num[n] <= num[n-1]) {n--;}
    				else { break;}
    			}
    			return n-1;
    		}
    		
    		private void swap (int[] num, int i, int j){
    			int tem = 0;
    			tem = num[j];
    			num[j] = num[i];
    			num[i] = tem;
    		}
    		
    		private void reverse (int[] num, int start){
    			int n = num.length-1;
    			while(n >= start){
    				swap(num, n, start);
    				n--;
    				start++;
    			}
    		}
    		
    		private int getFirstLarger(int[] num, int start){
    			int n = num.length-1;
    			int result = 0;
    			while(n>=0){
    				if(num[n] <= num[start]) {n--;}
    				else {result = n; break;}
    			}
    			return result;
    		}
    		
    		public void nextPermutation(int[] num) {
    	        int firstDeacrease = getFirstDecrease(num);
    	        
    	        if(firstDeacrease == -1) { reverse(num, 0); return;}
    	        int firstLarger = getFirstLarger(num, firstDeacrease);
    	        swap(num, firstDeacrease, firstLarger);
    	        reverse(num, firstDeacrease+1);
    	    }
    	}
    	
        public String getPermutation(int n, int k) {
        	NextPermutation nextPermut = new NextPermutation();
        	int[] array = new int[n];
        	for(int i=0; i<n; i++) array[i] = i+1;
        	for(int i=0; i<k-1; i++){
        		nextPermut.nextPermutation(array);
        	}
        	String result = "";
        	for(int i: array){
        		result+=i;
        	}
        	return result;
        }
    }

  • 0
    R

    will it be TLE?


Log in to reply
 

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