My Java AC Code


  • 0
    Q
    public String getPermutation(int n, int k) {
            int[] nums = new int[n];
            for(int i =0;i<n;++i){
                nums[i] = i+1;
            }
            while(--k > 0){
                PermutateNext(nums);
            }
            StringBuffer sb = new StringBuffer();
            for(int i =0;i<n ;++i){
                sb.append(nums[i]);
            }
            return sb.toString();
        }
        public void PermutateNext(int[] nums){
            int len = nums.length;
            if(len < 2) return;
            //寻找最后一对递增对
            int lastIncreas = 0;
            for(int i = len -2;i>=0;--i){
                if(nums[i] < nums[i+1]){
                    lastIncreas = i;
                    break;
                }
            }
    
            //寻找递增序之后元素中大于递增对中第一个值的最小值
            int minIndex = lastIncreas+1;
            int minmum = nums[minIndex];
            for(int i = lastIncreas +1;i<len;++i){
                if(nums[i] < minmum && nums[i] > nums[lastIncreas]){
                    minmum = nums[i];
                    minIndex = i;
                }
            }
            //递增对的第一个值和后边的最小值互换
            int tmp = nums[minIndex];
            nums[minIndex] = nums[lastIncreas];
            nums[lastIncreas] = tmp;
            //将递增对第一个值 后边的元素进行升序排列
            Arrays.sort(nums, lastIncreas + 1, len);
        }

Log in to reply
 

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