https://leetcode.com/problems/next-permutation/description/
A permutation of an array of integers is an arrangement of its members into a sequence or linear order.
- For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].
The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).
- For example, the next permutation of arr = [1,2,3] is [1,3,2].
- Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
- While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.
Given an array of integers nums, find the next permutation of nums.
The replacement must be in place and use only constant extra memory.
Example 1:
Input: nums = [1,2,3]
Output: [1,3,2]
Example 2:
Input: nums = [3,2,1]
Output: [1,2,3]
Example 3:
Input: nums = [1,1,5]
Output: [1,5,1]
Constraints:
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 100
대충 문제 이해는 된다.
뭔가 풀릴 거 같지만 역시나 time exceed에 걸릴 거 같은 안 좋은 느낌이 든다 .. ㅠ
1. Python
in-place 스위칭이 잘 안되어서 시간이 좀 걸렸다..
다시 검토가 필요한 문제!
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# MAXIMUM CASE
n = len(nums)
if nums == sorted(nums,reverse=True) :
for i in range(n//2):
nums[i],nums[n-1-i] = nums[n-1-i],nums[i]
return
## 아래 부분 다시 보고 판단해보자
for i in range(n - 2, -1, -1):
if nums[i] < nums[i + 1]:
# Find the next larger element to swap with nums[i]
for j in range(n - 1, i, -1):
if nums[j] > nums[i]:
nums[i], nums[j] = nums[j], nums[i]
break
# Sort the remaining part (right side of nums[i])
nums[i + 1:] = sorted(nums[i + 1:])
break
골자는 뒤에서부터 Retrieve를 해야한다는 것이었다.
2. C
이것 저것 귀찮은 것들을 미리 C 함수로 만들어놓자.
그냥 이제 C의 method 만드는 건 본능적으로 만들어 버린다.
void swap(int *a, int*b){
int temp = *a;
*a = *b;
*b = temp;
}
void reverse(int* lst, int start, int end){
while(start < end){
swap(&lst[start],&lst[end]);
start++;
end--;
}
}
void nextPermutation(int* nums, int numsSize) {
for(int i=numsSize-1;i>=1;i--){
if(nums[i]>=nums[i-1]){
for(int j=numsSize-1;j>=i;j--){
if(nums[j]>nums[i-1]){
swap(&nums[j],&nums[i-1]);
reverse(nums,i,numsSize-1);
return;
}
}
}
}
// Max value case
reverse(nums,0,numsSize-1);
}
3. C++ 그나마 쉬운 C++ case
class Solution {
public:
void reverse(vector<int>& lst, int s, int e){
while(s<e){
swap(lst[s],lst[e]);
s++;
e--;
}
}
void nextPermutation(vector<int>& nums) {
int n = nums.size();
int i = n-2;
while( i >= 0 && nums[i] >= nums[i+1]){
i--;
}
if(i>=0){
int j = n-1;
while(nums[j] <= nums[i]){
j--;
}
swap(nums[i],nums[j]);
}
reverse(nums,i+1,n-1);
}
};
재밌군 재밌어..!
