Share my O(n) time solution


  • 141
    Y

    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);
    }

  • 0
    C

    Similar idea.

    class Solution {
    public:
        void nextPermutation(vector<int> &num) {
            next_permutation(num.begin(), num.end());
        }
        
        template <class Iter>
        bool nextPermutation(Iter start, Iter end) {
            auto pivot = end-1;
            auto change = end-1;
    
            // find the pivot number
            while (pivot!=start && *pivot>=*(pivot+1)) {
                --pivot;
            }
            
            if (pivot==start) {
                reverse(start, end);
                return false;
            }
            
            // find the change number
            while (change!=pivot && *change<*pivot) {
                --change;
            }
            
            swap(*change, *pivot);
            reverse(pivot, end);
            return true;
        }
    };
    

    Sorry, the answer is not correct. The right one is :

    class Solution {
    public:
        void nextPermutation(vector<int> &num) {
            next_permutation(num.begin(), num.end());
        }
        
        template <class Iter>
        bool next_permutation(Iter start, Iter end) {
            const auto rstart = reverse_iterator<Iter>(end);
            const auto rend = reverse_iterator<Iter>(start);
            
            auto pivot = next(rstart);
            while (pivot!=rend && *pivot>=*prev(pivot)) {
                ++pivot;
            }
            
            if (pivot==rend) {
                reverse(rstart, rend);
                return false;
            }
            
            auto change = find_if(rstart, pivot, bind1st(less<int>(), *pivot));
            swap(*change, *pivot);
            reverse(rstart, pivot);
            return true;
        }
    };

  • 0
    W
    This post is deleted!

  • 0
    G

    sorry for my question.
    auto pivot = end - 1;
    Is it okay to use *(pivot + 1) in your while?


  • 0
    P
    void nextPermutation(vector<int> &num) {
        int index = num.size() - 2;
        int rIndex = index;
        //traverse forward till find first decending num, save in index
        for (; index >= 0; index--)
        {
            //find first num larger than nun[index], save in rIndex
            if (num[index + 1] > num[index])
            {
                for (rIndex = num.size() - 1; rIndex > index && num[index] >= num[rIndex]; rIndex--);
                swap(*(num.begin() + index), *(num.begin() + rIndex));
                break;
            }
        }
        reverse(num.begin() + index + 1, num.end());
    

    This is my code, FYI


  • 1
    K

    Now that you used a sort function, can this be O(n) totally?


  • 1
    Y

    I don't think this is a correct answer.

    void nextPermutation(vector<int> &num) {
    next_permutation(num.begin(), num.end());
    }
    already gives you an "accepted" result from OJ leetcode, but the bool nextPermutation(Iter start, Iter end) itself cannot pass all the test cases


  • 0
    D

    It is. The sort function is just reversing [start, end]. Since the range passed into that function is naturally sorted based on the way how we find it.


  • 27
    J

    Similar Solution, a bit fewer lines of code. Three steps:

    1. Reverse find first number which breaks descending order.
    2. Exchange this number with the least number that's greater than this number.
    3. Reverse sort the numbers after the exchanged number.
            public class Solution {
                  	public static void nextPermutation(int[] num) {
                		int i = num.length - 2;
                		for(; i >= 0 && num[i] >= num[i+1]; i--) 
                			;
                		
                		if(i >= 0) {
                			int j = i + 1;
                			for(; j<num.length && num[i] < num[j]; j++) 
                				;
                			exchange(num, i, j-1);
                		}
                		
                		i ++ ; 
                		int k = num.length - 1;
                		for(; i<k; i++, k--)
                			exchange(num, i, k);
                	}
                	
                	private static void exchange(int[] num, int i, int j) {
                		int t = num[i];
                		num[i] = num[j];
                		num[j] = t;
                	}
                }
    

  • 0
    W
    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());
    }

  • 22
    W

    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());
    }

  • 0
    S
    class Solution {
    public:
        void nextPermutation(vector<int> &num) {
            if ( is_sorted(num.rbegin(), num.rend())){
                reverse(num.begin(), num.end());
                return;
            }
            auto it = is_sorted_until(num.rbegin(), num.rend());
            iter_swap( it, find_if(num.rbegin(), num.rend(), [&](int v){ return v > *it;}));
            reverse(num.rbegin(), it);
        }
    };
    

    easy to understand and remember


  • 1
    L

    Just to provide another algorithm, which might be easier to follow.

    The idea of the algorithm is to find the "lowest" position in the number that we can switch to be a bigger number in the lower part of the number. Once we found this optimal switching point, we then rearrange the numbers on the right side of the switching point to make the final number minimal.

    Here are the breakdown steps of the above idea:

    Step 1). From right to left, for each number, we find the right-most number that it can switch. e.g. {1, 2, 3}, for number 3, the right-most number it can switch with is 2, but NOT 1.

    Step 2). Once we find the switching point for each number, we rank the “lowest” one, which is the optimal point to make the result minimal. Note: we can do Steps 1 and 2 in a single traversal.

    Step 3). We switch the number at the switching point with its pair number in Step 1.

    Step 4). We rearrange the numbers on the right side of the switching point in an ascendent order, to make the final result minimal.

    e.g. INPUT={4,2,0,2,3,2,0} (a real test case from OJ). The lowest position that we do the switch should be the number [2] in the middle which is to switch with number 3. The numbers on the right side of the switching point is then {2, 2, 0}, we then reorder them into {0, 2, 2}. So the final result is {4, 2, 0, 3, 0, 2, 2}.

    	private static void bubbleSort(int [] num, int start){
    		for(int i=start; i<num.length; i++){
    			for(int j=i; j<num.length; j++){
    				if(num[i] > num[j]){
    					int temp = num[i];
    					num[i] = num[j];
    					num[j] = temp;
    				}
    			}
    		}
    	}
    	
        public void nextPermutation(int[] num) {
    
    		int w = num.length - 1;
    		int max_i = -1, i_w = -1;
    		
    		while (w > 0) {
    			for (int i = w - 1; i >= 0; i--) {
    				if (num[w] > num[i]) {
    					if(i > max_i){
    						max_i = i;
    						i_w = w;
    					}
    				}
    			}
    			w--;
    		}
    		
    		if(max_i != -1){
    			// Find the best switching point.
    			int temp = num[max_i];
    			num[max_i] = num[i_w];
    			num[i_w] = temp;
    
    			// Do the bubble sort to get the minimal number.
    			bubbleSort(num, max_i + 1);
    
    		}else{
    			// Did not find any solution
    			Arrays.sort(num);
    		}
    }
    

  • 0
    S

    Pay attention to "Writing code? Select all code then click on the {} button to preserve code formatting.” above text editor.


  • 0
    L
    This post is deleted!

  • 0
    S

    similar idea
    (1)From right to left,find first digit which violate the increase call it partitionNumber
    (2)partitionNumber = -1 indicate largest ,should (3),if not From right to left,find first digit which large than partitionNumber call it changeNumber
    swap the partition index and changeNumber
    (3)reverse all the digit on the right of partition index

    class Solution {
    public:
        void nextPermutation(vector<int> &num) {
            int count = num.size();
            if(count == 0 || count == 1){
                return;
            }//if
            // From right to left,find first digit which violate the increase
            // call it partitionNumber
            int index;
            for(index = count-2;index >= 0;index--){
                if(num[index+1] > num[index]){
                    break;
                }//if
            }//for
            int tmp;
            // -1 indicate largest
            if(index != -1){
                // From right to left,find first digit which large than partitionNumber
                // call it changeNumber
                for(int i = count-1;i > index;i--){
                    if(num[index] < num[i]){
                        // swap the partition index and changeNumber
                        tmp = num[index];
                        num[index] = num[i];
                        num[i] = tmp;
                        break;
                    }//if
                }//for
            }//if
            // reverse all the digit on the right of partition index
            for(int i = index+1,j = count - 1;i < j;i++,j--){
                tmp = num[i];
                num[i] = num[j];
                num[j] = tmp;
            }//for
        }
    };
    

  • 1
    C

    good solution, easy to understand
    perhaps you can rename the function reverseSort to just reverse, to make things more clear, since its not really sorting


  • 0
    B
    def nextPermutation(num):
    
        # find the start of a descending sequence from the tail
    
        if not num:
            return []
    
        def swap(i,j):
            temp=num[i]
            num[i]=num[j]
            num[j]=temp
    
        def reverse(i,j):
            if i==j:
                return
            while i<j:
                swap(i,j)
                i+=1
                j-=1
    
    
        length=len(num)
        des_start=0
        for i in range(length-1,0,-1):
            if num[i-1]<num[i]:
                des_start=i
                break
    
        if des_start==0:
            reverse(0,length-1)
            return num
    
        place_to_change=des_start-1
    
        print(place_to_change,des_start)
    
        for i in range(length-1,place_to_change,-1):
            if num[i]>num[place_to_change]:
                swap(i,place_to_change)
                break
    
    
        reverse(des_start,length-1)
    
        return num
    

    this is the python code..


  • 0
    C

    nice and clear!!


  • 1
    J

    That's a good explaination!!!


Log in to reply
 

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