NextPermutation [source code]


public class NextPermutation {
static
/******************************************************************************/
class Solution {
    public void nextPermutation(int[] nums) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer> ();
        int max = Integer.MIN_VALUE, i = nums.length - 1;
        while (i >= 0) {
            if (pq.isEmpty () || max <= nums[i]) {          // has to include ==
                max = nums[i];
                pq.offer (nums[i]);
            } else break;
            i--;
        }
        if (i < 0) {
            while (!pq.isEmpty ())
                nums[++i] = pq.poll ();
            return;
        }
        int j = i + 1;
        while (!pq.isEmpty () && pq.peek () <= nums[i])     // has to include == : corresponds to above
            nums[j++] = pq.poll ();
        if (!pq.isEmpty ()) {
            int nums_i = nums[i];
            nums[i] = pq.poll ();
            pq.offer (nums_i);
        }
        while (!pq.isEmpty ())
            nums[j++] = pq.poll ();
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        NextPermutation.Solution tester = new NextPermutation.Solution();
        int[][] inputs = {
            {1,2,3}, {1,3,2},
            {1,1,5}, {1,5,1},
            {1,5,5}, {5,1,5},
            {3,2,1}, {1,2,3},
            {1,2,4,3}, {1,3,2,4},
            {2,3,1}, {3,1,2},
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            int[] nums = inputs[2 * i], ans = inputs[2 * i + 1];
            String input_str = Printer.array (nums), ans_str = Printer.array (ans);
            Printer.separator ();
            tester.nextPermutation (nums);
            String output_str = Printer.array (nums);
            System.out.printf ("[%s] -> [%s], expected: [%s]\n", 
                input_str, Printer.wrapColor (output_str, output_str.equals (ans_str) ? "green" : "red"), ans_str
            );
        }
    }
}

笨办法肯定是直接用permutation的方法去做, 但是这个明显就是陷入了我们之前说过的overkill的问题, 这个问题最后的最优解可能和通用的permutation解法有点关系, 但是肯定不是直接的搬运;

没有思路, 先笔算, 找找人逻辑;

另外注意一个坑, 这个题目没有说没有duplicate, 笔算的时候感觉这个可能会让问题复杂化;

Google的题目还是坑人, 这个题目思考了半天还是对于人逻辑毫无想法, 这种题目就真的是没思路; 一个简单的思路是尝试就直接把这个string的类似integer的hash计算出来, 然后用+1操作, 但是直觉上认为这种做法未必能成功, 而且加法的时候各种进位问题处理起来也很麻烦;

另外, example3已经是确认告诉你了, 有duplicate;

好像三位的例子不是很适合观察, 开始自己用四位的例子来观察. 实际做题的时候, 题目给的例子不合适不够typical是很常见的, 要有自己想例子的习惯和动力;

有一个大概的思路, 写写看;

一个例子需要面试官澄清: 1,5,5下一个是什么? OJ表示, 是5,1,5, 这个是有点counter intuitive的;

最后还是做出来了, 不过超时了, 速度是29ms (29%).

我的思路其实就是从end开始往左扫到一个最长的递减数列; 然后在停顿位置放上这个递减数列里面最小的但是比停顿位置大的数字; 总体讲, 我觉得这题我还是挺动了脑子的; 最后的算法的复杂度也满意; 这题的AC rate其实不高, 不丢人好吧. again, 要自己找到一个最typical的例子, 我用的是1,2,4,3. 一个intuition就是, 对于一个subarray, 当全部递减的时候, 他是最大的, 当全部递增的时候, 他是最小的; 所以找到一个最大的right subarray, 类似加法的时候找999这样的东西, 然后给他变成000, 讲道理, 这个题目真的有意思;

递增/递减Stack: max/min

这题的数据结构的选择也有讲究. 虽然我们是维护一个递减数列, 你的第一感觉肯定是用Stack, 但是这题用Stack我感觉其实不如用PriorityQueue? 不对想想好像用Stack也行, 反正维护sorted的, 最后找替换element的时候也不麻烦; 反正PriorityQueue也行好吧.

维护longest递增递减数列的方法其实以前也没有正儿八经写过; 当然你可以用peek来不停的跟candidate进行对比, 我这里是另外一个方法, 用最值来进行比较: 因为维护的是一个sorted的结构, 所以最值跟peek其实是一样的效果; 注意我这里的使用方法. 我的PriorityQueue的peek实际上是min, 但是我单独维护一个max; 这样我最后把东西从PriorityQueue里面往外倒找替换element的时候, 会更方便一些;

editorial

Approach #1 Brute Force [Time Limit Exceeded]

Algorithm

In this approach, we find out every possible permutation of list formed by the elements of the given array and find out the permutation which is just larger than the given one. But this one will be a very naive approach, since it requires us to find out every possible permutation which will take really long time and the implementation is complex. Thus, this approach is not acceptable at all. Hence, we move on directly to the correct approach.

Approach #2 Single Pass Approach [Accepted]

First, we observe that for any given sequence that is in descending order, no next larger permutation is possible. For example, no next permutation is possible for the following array: [9, 5, 4, 3, 1]

就跟我的想法是一样的; 有这个想法, 这个题目基本就有思路了; 

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

    private void reverse(int[] nums, int start) {  
        int i = start, j = nums.length - 1;  
        while (i < j) {  
            swap(nums, i, j);  
            i++;  
            j--;  
        }  
    }  

    private void swap(int[] nums, int i, int j) {  
        int temp = nums[i];  
        nums[i] = nums[j];  
        nums[j] = temp;  
    }  
}

这个算法确实比我的算法更简练一些; 同样, 注意他这里等号的处理, 也是为了handle duplicate;

@yuyibestman said in Share my O(n) time solution:

My idea is for an array:

  1. Start from its last element, traverse backward to find the first one with index i that satisfy num[i-1] < num[i]. So, elements from num[i] to num[n-1] is reversely sorted.
  2. To find the next permutation, we have to swap some numbers at different positions, to minimize the increased amount, we have to make the highest changed position as high as possible. Notice that index larger than or equal to i is not possible as num[i,n-1] is reversely sorted. So, we want to increase the number at index i-1, clearly, swap it with the smallest number between num[i,n-1] that is larger than num[i-1]. For example, original number is 121543321, we want to swap the '1' at position 2 with '2' at position 7.
  3. The last step is to make the remaining higher position part as small as possible, we just have to reversely sort the num[i,n-1]

The following is my code: 

    public void nextPermutation(int[] num) {  
        int n=num.length;  
        if(n<2)  
            return;  
        int index=n-1;          
        while(index>0){  
            if(num[index-1]<num[index])  
                break;  
            index--;  
        }  
        if(index==0){  
            reverseSort(num,0,n-1);  
            return;  
        }  
        else{  
            int val=num[index-1];  
            int j=n-1;  
            while(j>=index){  
                if(num[j]>val)  
                    break;  
                j--;  
            }  
            swap(num,j,index-1);  
            reverseSort(num,index,n-1);  
            return;  
        }  
    }  

    public void swap(int[] num, int i, int j){  
        int temp=0;  
        temp=num[i];  
        num[i]=num[j];  
        num[j]=temp;  
    }  

    public void reverseSort(int[] num, int start, int end){     
        if(start>end)  
            return;  
        for(int i=start;i<=(end+start)/2;i++)  
            swap(num,i,start+end-i);  
    }

跟editorial实际上是差不多的思想;

非常简练的另一个:

@wjtian said in Share my O(n) time solution:

My O(N) Code: 

    void nextPermutation(vector<int> &num) {  
        if(num.size()<=1) return;  
        int i=num.size()-1,j;  
        for(j=num.size()-2; j>=0; j--){  
            if(num[j]<num[j+1]) break;  
        }  
        if(j>=0){  
            while(num[i]<=num[j]) i--;  
            swap(num[i], num[j]);  
        }  
        reverse(num.begin()+j+1, num.end());  
    }

等于说这个题目实际上Wiki上面就是有代码的:

@jianchao.li.fighter said in A simple algorithm from Wikipedia with C++ implementation (can be used in Permutations and Permutations II):

Well, in fact the problem of next permutation has been studied long ago. From the [Wikipedia page][1], in the 14th century, a man named Narayana Pandita gives the following classic and yet quite simple algorithm (with minor modifications in notations to fit the problem statement):

  1. Find the largest index k such that nums[k] < nums[k + 1]. If no such index exists, the permutation is sorted in descending order, just reverse it to ascending order and we are done. For example, the next permutation of [3, 2, 1] is [1, 2, 3].
  2. Find the largest index l greater than k such that nums[k] < nums[l].
  3. Swap the value of nums[k] with that of nums[l].
  4. Reverse the sequence from nums[k + 1] up to and including the final element nums[nums.size() - 1].

Quite simple, yeah? Now comes the following code, which is barely a translation.

Well, a final note here, the above algorithm is indeed powerful --- it can handle the cases of duplicates! If you have tried the problems [Permutations][2] and [Permutations II][3], then the following function is also useful. Both of [Permutations][4] and [Permutations II][5] can be solved easily using this function. Hints: sort nums in ascending order, add it to the result of all permutations and then repeatedly generate the next permutation and add it ... until we get back to the original sorted condition. If you want to learn more, please visit [this solution][6] and [that solution][7]. 

class Solution {  
    void nextPermutation(vector<int>& nums) {  
      int k = -1;  
      for (int i = nums.size() - 2; i >= 0; i--) {  
          if (nums[i] < nums[i + 1]) {  
              k = i;  
              break;  
          }  
      }   
      if (k == -1) {  
          reverse(nums.begin(), nums.end());  
          return;  
      }  
      int l = -1;  
      for (int i = nums.size() - 1; i > k; i--) {  
          if (nums[i] > nums[k]) {  
              l = i;  
              break;  
          }   
      }   
      swap(nums[k], nums[l]);  
      reverse(nums.begin() + k + 1, nums.end());   
    }  
};

[1]: http://en.wikipedia.org/wiki/Permutation

[2]: https://leetcode.com/problems/permutations/

[3]: https://leetcode.com/problems/permutations-ii/

[4]: https://leetcode.com/problems/permutations/

[5]: https://leetcode.com/problems/permutations-ii/

[6]: https://leetcode.com/discuss/38255/solution-nextpermutation-permutations-without-modification

[7]: https://leetcode.com/discuss/38260/easy-solution-using-code-in-nextpermutation

另外一个有趣的理解方式:

@cdai said in A simple algorithm from Wikipedia with C++ implementation (can be used in Permutations and Permutations II):

I think another view to understand this solution is to draw the Tree, namely search space, of the permutation.
The next permutation is actually the next leaf on the DFS path. Then it may be easier to review this solution:

  • Step-1: The internal node on the path that represents nums[0...k-1] is the LCA (Lowest Common Ancestor) of current permutation (leaf) and the next one we want.
    • Step-2: nums[0..k-1] + nums[l] is the child node of LCA that goes to next permutation.
    • Step-3: reverse all the remaining nums means we goes for the first leaf in this subtree.

Hope I get it right and you know what I'm talking about...

0_1482546585830_1773271831.jpg

有人说的对, 实际上这里第二部那个搜swap点的, 可以改成binary search:

@kunyi731 said in A simple algorithm from Wikipedia with C++ implementation (can be used in Permutations and Permutations II):

Great explanation. I have the same idea, only for the actual implementation slightly simpler code.

I guess it's noteworthy that the linear search step to find nums[i] > nums[k-1] can be replaced by binary search. In that way the overall complexity is still O(n) but it might slightly over-perform the simple solution in long sequences.

看了一下discussion, 这个题目原来一点都不trivial, 没想到我居然还是想出来了;

discussion其他基本都是模仿这个swap的做法的, 好像没有多少ad-hoc的做法, 跟我这样的;

submission基本波动. 他们这个swap的做法好像也不比我的做法快;

Problem Description

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, do not allocate 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

Difficulty:Medium
Total Accepted:138.9K
Total Submissions:479.2K
Contributor:LeetCode
Companies
google
Related Topics
array
Similar Questions
PermutationsPermutations IIPermutation SequencePalindrome Permutation II

results matching ""

    No results matching ""