[leetcode]31. Next Permutation

31. Next Permutation

 

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

 

class Solution(object):
    def sort(self, nums, start ):
        for i in range(start, len(nums)-1):
            min_index = i
            for j in range(i+1, len(nums)):
                if nums[j] < nums[min_index]:
                    min_index =j
            if min_index != i :
                nums[min_index] , nums[i] = nums[i], nums[min_index]
        
        
    def getNext(self, nums, start ):
        if start >= len(nums)-1:
            return False
        
        IsChanged = self.getNext(nums, start+1)
        if IsChanged:
            return True
        nextNum = -1 
        for i in range(start+1,len(nums)):
            if nums[start]<nums[i] and (nextNum <0  or nums[nextNum] > nums[i]):
                nextNum = i 
        if nextNum < 0 :
            return False
        else :
            nums[start], nums[nextNum] = nums[nextNum], nums[start]
            self.sort(nums, start+1)
        return True
        
    
    def nextPermutation(self, nums):
        IsChanged = self.getNext(nums, 0)
        if IsChanged :
            return 
        else :
            nums.sort()
            return 

getNext를 통해서 현재 위치보다 오른쪽에 있는 것들중에 더 큰 수가 잇는지 확인하고, 그 큰수들 중에 가장 작은 수와 현재 위치를 바꾸고 

현재 위치 다음부분을 정렬한다. in-place라서 선택정렬로 정렬을 할 수 있도록 했다.

BigO(N^2)일 것같다.

 

하지만 좋은 코드를 보고 큰 깨달음을 얻었는데, 

사실 현재 위치보다 오른쪽에 자신보다 큰수가 없다는 것은 현재 위치로부터 오른쪽으로 내림차순 정렬 되어있다는 것이고 

그것을 반복적으로 하다가 현재 위치보다 오른쪽에 큰수가 있을때에는 그 오른쪽은 이미 내림차순 정렬 되어있다고 가정해도 좋다는 것이다.  그러면 현재 위치의 숫자와 가장 오른쪽 끝 숫자부터 비교하다가 현재 위치 숫자보다 큰 수를 발견하고 교환을 한다는 것은 오른쪽에 있는 수중에 현재 숫자보다는 크면서 오른쪽에 있는 숫자중에서는 작은편에 속하는 숫자를 선택했다는 것을 보장할 수 있다.

그러면 그 두 수를 교환하고 나서도 원래 현재숫자는 오른쪽에 있던 숫자보다는 더 작으므로 자리가 바뀌여도 내림차순 정렬 되어있다는 것을 보장 할 수 있으며, 그말은 즉 오른쪽 부분을 reverse하면 오름차순으로 정렬된다는 것과 같은 의미가 될 것이다.

WOW 정말 대단하다.

class Solution(object):
    
    def nextPermutation(self, nums):
        i = len(nums)-1
        
        while i>0 and nums[i] <= nums[i-1]:
            i -=1
        if i==0:
            nums.reverse()
            return
        changePoint = i-1
        j = len(nums)-1
        
        while j>=0 and nums[changePoint] >= nums[j]:
            j -=1
        nums[changePoint], nums[j] = nums[j], nums[changePoint]
        l = changePoint+1
        r = len(nums)-1
        
        while l < r:
            nums[l] , nums[r] = nums[r], nums[l]
            l +=1
            r -=1
        
        return 

그리고 이 코드에서 신경써야 할 점은 <=  과 < 어떤 선택을 할 지이다.

nums[i] < nums[i-1]: 인 경우에는

num[i]== nums[i-1]에도 멈추고 변경하려고 하므로 <= 해야한다.