Sharing my clean and easy-understand java code with explanation


  • 105
    S
    public class Solution {
        public void nextPermutation(int[] nums) {
          if(nums.length<=1){
              return;
          }
          
          int i= nums.length-1;
          
          for(;i>=1;i--){
             
             if(nums[i]>nums[i-1]){ //find first number which is smaller than it's after number
                 break;
             }
          }
          
          if(i!=0){
              swap(nums,i-1); //if the number exist,which means that the nums not like{5,4,3,2,1}
          }
          
          reverse(nums,i);    
        }
        
        private void swap(int[] a,int i){
            for(int j = a.length-1;j>i;j--){
                if(a[j]>a[i]){
                    int t = a[j];
                    a[j] = a[i];
                    a[i] = t;
                    break;
                }
            }
        }
        
        private void reverse(int[] a,int i){//reverse the number after the number we have found
            int first = i;
            int last = a.length-1;
            while(first<last){
                int t = a[first];
                a[first] = a[last];
                a[last] = t;
                first ++;
                last --;
            }
        }
        
    }
    

    在当前序列中,从尾端往前寻找两个相邻元素,前一个记为first,后一个记为second,并且满足first 小于 second。然后再从尾端寻找另一个元素number,如果满足first 小于number,即将第first个元素与number元素对调,并将second元素之后(包括second)的所有元素颠倒排序,即求出下一个序列

    example:
    6,3,4,9,8,7,1
    此时 first = 4,second = 9
    从尾巴到前找到第一个大于first的数字,就是7
    交换4和7,即上面的swap函数,此时序列变成6,3,7,9,8,4,1
    再将second=9以及以后的序列重新排序,让其从小到大排序,使得整体最小,即reverse一下(因为此时肯定是递减序列)
    得到最终的结果:6,3,7,1,4,8,9


  • 0
    X

    It's real an easy understand solution


  • 10
    H

    tai ji zhi le 66666


  • 13
    H

    Based on your explanation, I wrote a cleaner code. Thanks for sharing!

    public class Solution {
        public void nextPermutation(int[] nums) {
            // find two adjacent elements, n[i-1] < n[i]
            int i = nums.length - 1;
            for (; i > 0; i --) {
                if (nums[i] > nums[i-1]) {
                    break;
                }
            }
            if (i != 0) {
                // swap (i-1, x), where x is index of the smallest number in [i, n)
                int x = nums.length - 1;
                for (; x >= i; x --) {
                    if (nums[x] > nums[i-1]) {
                        break;
                    }
                }
                swap(nums, i - 1, x);
            }
            reverse(nums, i, nums.length - 1);
        }
        
        void swap(int[] a, int i, int j) {
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
        // reverse a[i, j]
        void reverse(int[] a, int i, int j) {
            for (; i < j; i ++, j --) {
                swap(a, i, j);
            }
        }
    }

  • 1
    U

    Good explanation!


  • 5
    O

    The example is really good for understanding the algorithm. Just translate it to English version for your reference.

    [6,3,4,9,8,7,1]
         i-1 i    k
    

    (1) leftward find the first decreasing number @ index i - 1, (4)
    (2) then nums[i:] must be rightward decreasing (9,8,7,1)
    (3) leftward find the first number that is larger than i - 1, which is at k, (7)
    (4) swap i - 1 with k, (6,3,7,9,8,4,1). we can see that nums[i:] will still be rightward decreasing (9,8,4,1)
    (5) But we need them to be rightward increasing so that it's the smallest after swapping, so we reversed nums[i:], which get the result (6,3,7,1,4,8,9)


  • 0
    W

    666666666666666666


  • 0
    L

    I think this problem will make people misunderstanding,for example,if the input
    is [1,321,64],then I think the 'lexicographically next greater permutation' should be [1,64,321],but your algorithm result is [64,1,321].am I think wrong?@sunnyChen18


  • 0
    C

    666 !!!you are legendary!!


  • 1
    N

    @leetcodeLeon
    The next lexicographical permutation of [1, 321, 64] is [64, 1, 321]. If you read Lexicographical order Wikipedia page carefully, you will understand.


  • 0
    J

    If you share a solution, please also share the reasoning behind it. Thanks.


  • 0
    G

    clever solution!


  • 3
    L

    @sunnyChen18 Good algorithm!
    Big God, Please receive my knee!


  • 0

    @hukun01 agree, it's clearer to break out the "swap with smallest element greater than new element" part.

        public void NextPermutation(int[] nums) 
        {
            if (nums == null || nums.Length < 2) return;
            
            // from end backwards - find last elem where sequence is equal or increasing
            int head = nums.Length - 1;
            while (head > 0 && nums[head - 1] >= nums[head]) head--;
    
            if (head > 0) 
            {
                // we need to incorporate the next elem to further the sequence
                // swap the new element with the smallest element in the sequence that is larger than the new element
                int newHead = head;
                while (newHead < nums.Length - 1 && nums[head - 1] < nums[newHead + 1]) newHead++;
                Swap(nums, head - 1, newHead);
            }
        
            // reverse chars from the head to end of sequence
            // this will give the lowest permutation with this head
            Reverse(nums, head, nums.Length - 1);
        }
        
        public void Reverse(int[] nums, int i, int j)
        {
            for (; i < j; i++, j--) Swap(nums, i, j);
        }
    
        public void Swap(int[] nums, int i, int j)
        {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    

  • 0
    S

    太给力。支持大神。这种题真是费脑子。不知道po多久想出来的


  • 0
    R

    @sunnyChen18 Nice solution. A slight improvement is to use binary search after locating the 'first' element. Time would still be O(n) though.


  • 1
    L

    you explanation helps me, thanks


  • 0
    S

    @Lanzevasar You are welcome!


  • 0

    I have to say: 6 fly!


  • 0
    S

    66666666666666


Log in to reply
 

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