31. Next Permutation

# Hard

• Find the element should be replaced, [1, 2, 7, 6, 5, 4], 2 is the number.

• find the element just a little larger than 2, swap(2, 4) --- can save time

• reverse [7, 6, 5, 2]

• result -> [1, 2, 4, 2, 5, 6, 7]

Java(O(N*log N)

class Solution {
    public void nextPermutation(int[] nums) {
        if(nums.length == 1) return;
        
        // [i, -1] should be rearranged
        int i = nums.length - 2;
        for(; i >= 0; i --) 
            if(nums[i] < nums[i+1]) 
                break;
        
        // find the index j which number is just bigger than nums[i]
        Arrays.sort(nums, i+1, nums.length);
        if(i == -1) return;  // [3, 2, 1]
        
        int j = insertPosition(nums, i+1, nums[i]);
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    private int insertPosition(int[] nums, int i, int goal) {
        int left = i, right = nums.length - 1;
        while(left < right) {
            int mid = left + (right - left)/2;
            if(goal >= nums[mid])
                left = mid +1;
            else
                right = mid;
        }
        return left;
    }
}

Java(O(N))

class Solution {
    public void nextPermutation(int[] nums) {
        if(nums.length == 1) return;
        
        // [i, -1] should be rearranged
        int i = nums.length - 2;
        while(i >= 0 && nums[i] >= nums[i+1])
            i --;
        if(i == -1) {
            reverse(nums, 0);
            return;
        }
        
        // find the index j which number is just bigger than nums[i]
        int j = nums.length - 1;
        while(nums[j] <= nums[i])
            j --;
        
        swap(nums, i, j);
        reverse(nums, i+1);
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    private void reverse(int[] nums, int start) {
        int i = start, j = nums.length-1;
        while(i < j) {
            swap(nums, i, j);
            i ++;
            j --;
        }
    }
}

Python

// Some code
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if nums == sorted(nums, reverse=True):
            nums.reverse()
            return nums
        
        # find the element need to be replaced
        for i in reversed(range(len(nums)-1)):
            if nums[i] < nums[i+1]:
                break
        
        # replace this element with the element a little big than it
        a = nums[i]
        replace = i + 1
        for j in range(i+2, len(nums)):
            if nums[j] > a and nums[j] < nums[replace]:
                replace = j
        temp = nums[replace]
        nums[replace] = nums[i]
        nums[i] = temp
        
        # sort the right side elements in acending order
        nums[i+1:] = sorted(nums[i+1:])
        
        return nums