O(n) Solution Java and Python


  • 0
    F

    Java:

    public void nextPermutation(int[] nums) {
            if (nums == null || nums.length == 0) return;
            int k = -1;
            for (int i = nums.length - 2; i >= 0; i--) {
                if (nums[i] < nums[i + 1]) {
                    k = i;
                    break;
                }
            }
            if (k == -1) {
                swap(nums, 0, nums.length - 1) ;
                return;
            }
            int right = nums.length - 1;
            while (right > k && nums[right] <= nums[k]) right--;
            int temp = nums[k];
            nums[k] = nums[right];
            nums[right] = temp;
    
            swap(nums, k + 1, nums.length - 1);
    
        }
        private void swap(int[] nums, int right, int left) {
            for (int i = right, j = left; i < j; i++, j--) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
    

    Python:

    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """       
        if nums is None or len(nums) <= 1:
            return
        k = -1;
    
        for i in range(len(nums) - 2, -1, -1):
                if nums[i] < nums[i + 1]:
                    k = i
                    break
        if k == -1:
            nums.reverse()
            return
    
        right = len(nums) - 1
    
        while right > k and nums[right] <= nums[k]:
            right -= 1
    
        nums[k], nums[right] = nums[right], nums[k]
        nums[k + 1:len(nums)] = nums[len(nums) - 1:k:-1]
    

    My python not very good, just began to learn.


Log in to reply
 

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