Share my Python solution (Narayana Pandita's algorithm)


  • 0
    D

    comment embedded.

    class Solution:
        # @param {integer[]} nums
        # @return {void} Do not return anything, modify nums in-place instead.
        def nextPermutation(self, nums):
            '''
            Narayana Pandita's algorithm
            1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
            2. Find the largest index l greater than k such that a[k] < a[l].
            3. Swap the value of a[k] with that of a[l].
            4. Reverse the sequence from a[k + 1] up to and including the final element a[n].
            '''
            # scan backward to find the first element that is bigger than the element before it
            i = len(nums) - 1
            while i > 0 and nums[i] <= nums[i-1]:
                i -= 1
            if i > 0:
                # find the smallest number after nums[i] that is bigger than nums[i-1]
                j = len(nums) - 1
                while nums[j] <= nums[i-1]:
                    j -= 1
                # swap nums[j] with nums[i-1]
                nums[i-1], nums[j] = nums[j], nums[i-1]
            # reverse the part after i
            nums[i:] = reversed(nums[i:])

Log in to reply
 

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