leetcode 31. Next Permutation 谷歌面试题

Seawolf

另一道Google 面试题！

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

import java.util.*;

public class Solution {
        
        static ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        
        static ArrayList<Integer> list = new ArrayList<Integer>();
        
        public static void main(String[] args) {
                
                int[] array = {4,3,2,1};
                
                nextPermutation(array);

       for(int i = 0; i< array.length; i++) {
               
               System.out.println(array[i]);
       }

                
        }
        
        public static void permute(ArrayList<Integer> lst, ArrayList<ArrayList <Integer>> result, int[] input) {
                
                if(lst.size() == input.length) {
                        
                        result.add(new ArrayList<Integer>(lst));
                        return;
                        
                }
                
                for(int i = 0; i < input.length; i++) {
                        
                        if(lst.contains(input[i])) {
                                
                                continue;
                                
                        }
                        
                        lst.add(input[i]);
                        
                        permute(lst,result,input);
                        
                        lst.remove(lst.size()-1);
                        
                }
                
        }
        
    public static void nextPermutation(int[] nums) {
        
        int[] base = Arrays.copyOf(nums, nums.length);
        
        Arrays.sort(nums);
        
        permute(list, result, nums);
        
        for(int i = 0 ; i < result.size(); i++){
                
                boolean is = false;
                
                int count = 0;
                
                for(int x = 0; x< base.length; x++) {
                        
                        if(base[x] == result.get(i).get(x)) {
                                                            
                                count++;
                        }
                }
                
                if(count == base.length) {
                        
                        is = true;
                }
            
            if(is && i != result.size()-1){
                
                
                for(int j = 0; j < nums.length; j++){
                    
                    nums[j] = result.get(i+1).get(j);
                }
                
            }
            
            else if (is && i == result.size()-1){
                
                for(int j = 0; j < nums.length; j++){
                    
                    nums[j] = result.get(0).get(j);
                }
            }
        }
        
    }

}

这个代码可以算出给定数组的所有可能的排列，但是还是有一个比较大的问题，就是给定的数组如果含有重复的元素，那么这个方法将会失效，因为permute方法里面是以contains作为判断条件的。
所以对以上代码进行修改，使之可以兼容repeated number。

import java.util.*;

public class Solution {
        
        static ArrayList<ArrayList <Integer>> result = new ArrayList<>();
        
        public static void main(String[] args) {
                
                int[] nums = {1,2};
                
                int[] base = Arrays.copyOf(nums, nums.length);
                
                Arrays.sort(nums);
                
                permute(result, nums,0,nums.length);
        
        
//            System.out.println(result);
            
        for(int i = 0 ; i < result.size(); i++){
                
                boolean is = false;
                
                int count = 0;
                
                for(int x = 0; x< base.length; x++) {
                        
                        if(base[x] == result.get(i).get(x)) {
                                                            
                                count++;
                        }
                }
                
                if(count == base.length) {
                        
                        is = true;
                }
            
            if(is && i != result.size()-1){
                
                
                for(int j = 0; j < nums.length; j++){
                    
                    nums[j] = result.get(i+1).get(j);
                }
                
            }
            
            else if (is && i == result.size()-1){
                
                for(int j = 0; j < nums.length; j++){
                    
                    nums[j] = result.get(0).get(j);
                }
            }
        }
        
        
        for(int p = 0; p< nums.length; p++) {
                
                System.out.println(nums[p]);
        }
                
        }
        
        public static void permute(ArrayList<ArrayList <Integer>> result, int[] input, int i ,int length) {
                
                if(i == length-1) {
                        
                        ArrayList<Integer> list = new ArrayList<Integer>();
                        
                        for(int n = 0 ; n< input.length; n++) {
                                
                                Integer mm = new Integer(input[n]);
                                list.add(mm);
                        }
                                
                        result.add(list);
                        return;
                        
                }
                
                for(int j = i; j < length; j++) {
                        
                        if(!isExist(input,i,j)) {
                                
                                swap(input, i ,j);
                                
                                permute(result,input,i+1,input.length);
                                
                                swap(input, i,j);
                                
                        }
                        
                }
                
        }
        
        public static boolean isExist(int[] lst, int i, int j) {
                
                for(int x = i ; x < j ; x++) {
                        
                        if(lst[x] == lst[j]) {
                                
                                return true;
                                
                        }
                }
                
                return false;
        }
        
        public static void swap(int[] lst ,int i, int j) {
                
                int temp = lst[j];
                
                lst[j] = lst[i];
                
                lst[i] = temp;
        }

}

尽管答案是正确的，提交leetcode依然会报错。



原因是因为题目中要求只允许只用 constant extra memory.

实现方法：

1.从 input list a[n] 的倒数第二位开始向前循环，找到第一个下降序列，记为index1
2.从input list a[n] 的倒数第一位开始向前循环，找到第一个大于a[index1] 的元素 index2
3. 交换 index1 和 index2 对应的元素
4.对 index2 + 1 到 a.length -1 之间的元素进行 reverse 得到 nextpermutation


Here is the code:

import java.util.*;

public class Solution {
        
        public static void nextPermutation(int[] nums)  {
                
                
                int start = nums.length -2;
                
                while(start >= 0 && nums[start] >= nums[start +1]) {
                        
                        start --;
                }
                
        if(start >= 0){
            
                     int end = nums.length -1;    
            
            while(end >= 0 && nums[end] <= nums[start]){
                
                end -- ;
            }
            
            swap(nums,start,end);
        }
                
                
                reverse(nums, start+1);
                
                
        }
        
        public static void reverse(int[] nums, int i) {
        
        int len = nums.length-1;
                
                while(i < len) {
                        
                        swap(nums, i++ , len--);
                }
        }
        
        public static void swap(int[] nums, int i, int j) {
                
                int temp = nums[i];
                
                nums[i] = nums[j];
                
                nums[j] = temp;
        }
}