[C++][Java] Clean Code with Really Simple Explanation


  • 5

    To understand this approach, we need to define 2 concept with a 5 digit example 12543:

    • NCR - No Capacity Range : the number in that range cannot be bigger, Like: "543"
    • DWC - Digit With Capacity : A digit bring capacity to the range after it. Like: "[2]543"

    Let's get some hint from finding the Next Decimal:

    Next Decimal
    [5](9 9 9) <- NCR (No Capacity Range)
     ^
    DWC (Digit With Capacity)
    =>
    [6](0 0 0)
    

    Imagine how you increase this number 5999 to 6000:
    Because the first 3 digits from right is a No Capacity Range, you have to flip the 4th digits (5, the first Digit With Capacity.), to what - The next smallest digits greater than 5, which is 6, then make the rest 3 digits the smallest combination, which is "000", that's how you get this "6000";

    In an permutation though, the next smallest number for DWC(Digit With Capacity) would be whatever is available in that following NCR(No Capacity Range)

    Next Permutation
    1[2](5 4 3) <- NCR (No Capacity Range)
      ^
    DWC (Digit With Capacity)
    =>
    1[3](2 4 5)
    

    So we have found the pattern is always to find the first DWC(Digit With Capacity), then minimize the NCR after it.

    To summarize:

    1. Find the first DWC, which is 2;
    1[2](5 4 3)
      ^
    
    1. Reverse the NCR after it to make the NCR in increasing order(because it is already sorted in descending order).
    1[2](3 4 5)
      ^
    
    1. Swap the DWC with the 1st digit in the reversed range that is slightly bigger than it.
    1[3](2 4 5)
      ^--^
    

    DONE!

    C++

    class Solution {
    public:
        void nextPermutation(vector<int>& a) {
            if (a.size() <= 1) return;
            int dwc = -1; // Digit With Capacity
            for (int i = a.size() - 2; i >= 0; i--) {
                if (a[i] < a[i + 1]) {
                    dwc = i; break;
                }
            }
            // if dwc is not found, means this is a max array, reverse whole array and return;
            reverse(a.begin() + dwc + 1, a.end());
            if (dwc != -1) return;
            for (int i = dwc + 1; i < a.size(); i++) {
                if (a[i] > a[dwc]) {
                    swap(a[i], a[dwc]); break;
                }
            }
        }
    };
    

    Java

    /**
     * 0. For permutation of index, the smallest order is ever increasing, the largest order is ever decreasing.
     * 1. no-capacity-range: NCR - Start from the end, as long as the next number is bigger, this whole range have no capacity.
     * 2. First digit-with-capacity: DWC - find the first DWC index. reverse the rest. then switch the index with the first larger than index on the right.
     */
    public class Solution {
        public void nextPermutation(int[] a) {
            if (a.length < 2) return;
            /* Find the first Digit With Capacity */
            int dwc = -1;
            for (int i = a.length - 2; i >= 0; i--) {
                if (a[i] < a[i + 1]) {
                    dwc = i; break;
                }
            }
            /* Reverse the No Capacity Range after 1st DWC. */
            reverse(a, dwc + 1, a.length - 1);
            if (dwc != -1) {
                for (int i = dwc + 1; i < a.length; i++) {
                    if (a[i] > a[dwc]) {
                        swap(a, dwc, i); break;
                    }
                }
            }
        }
        private void reverse(int[] a, int i, int j) {
            for (; i < j; i++, j--) { swap(a, i, j); }
        }
        private void swap(int[] a, int i, int j) {
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }
    

Log in to reply
 

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