1ms O(n) solution


  • 0
    I
    public void nextPermutation(int[] array) {
            if(array != null && array.length > 1){
                int length = array.length;
                int start = length - 1;
                int end = start - 1;
                while(end >= 0 && array[start] <= array[end]){
                    end--;
                    start--;
                }
                if(end < 0){
                    // reverse all
                    reverse(array, 0, array.length - 1);
                }
                else {
                    // swap
                    int nAtEnd = array[end];
                    int toSwap = end;
                    while (toSwap < array.length - 1 && nAtEnd < array[toSwap + 1]){
                        toSwap++;
                    }
                    swap(array, end, toSwap);
                    reverse(array, end + 1, array.length - 1);
                }
            }
        }
        
        private void reverse(int[] array, int l, int r){
            while (l <= r){
                swap(array, l++, r--);
            }
        }
    
        private void swap(int[] array, int l, int r){
            int temp = array[l];
            array[l] = array[r];
            array[r] = temp;
        }
    

Log in to reply
 

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