In the Leetcode Next Permutation problem solution 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
Solution in C Programming
#include <limits.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#if defined(_MSC_VER)
#define FORCE_INLINE __forceinline
#else
#define FORCE_INLINE __attribute__((always_inline)) inline
#endif
FORCE_INLINE static void swap(int *restrict v1, int *restrict v2)
{
int tmp = *v1;
*v1 = *v2;
*v2 = tmp;
}
static int quicksortCompare(const void *v1, const void *v2)
{
return *(int *)v1 - *(int *)v2;
}
static int splitArray(int *nums, int numsSize)
{
for (int right = numsSize - 1; right >= 1; right--)
if (nums[right] > nums[right - 1])
return right;
return 0;
}
static int searchMinValueIdx(int *restrict nums, int numsSize, int leftIdx, int rightIdx)
{
const int pivot = nums[leftIdx];
int minVal = INT_MAX, minValIdx = -1;
for (; rightIdx < numsSize; rightIdx++)
{
if (nums[rightIdx] > pivot && nums[rightIdx] < minVal)
{
minVal = nums[rightIdx];
minValIdx = rightIdx;
}
}
return minValIdx;
}
static bool __nextPermutation(int *nums, int numsSize)
{
if (numsSize <= 1)
return false;
const int rightArrayIdx = splitArray(nums, numsSize);
if (rightArrayIdx == 0 && numsSize > 0)
{
return __nextPermutation(nums + 1, numsSize - 1);
}
else
{
const int leftArrayIdx = rightArrayIdx - 1;
const int minValIdx = searchMinValueIdx(nums, numsSize, leftArrayIdx, rightArrayIdx);
swap(&nums[leftArrayIdx], &nums[minValIdx]);
qsort(nums + rightArrayIdx, numsSize - rightArrayIdx, sizeof(nums[0]), quicksortCompare);
}
return true;
}
void nextPermutation(int *nums, int numsSize)
{
if (numsSize > 1)
{
if (__nextPermutation(nums, numsSize) == false)
{
qsort(nums, numsSize, sizeof(nums[0]), quicksortCompare);
}
}
}Solution in C++ Programming
class Solution {
public:
void nextPermutation(vector<int>& nums) {
// find the number before the last peak
int i = nums.size() - 2;
while(i >= 0 && nums.at(i) >= nums.at(i + 1)) i--;
// find the number just larger than our number at position i and swap
if(i >= 0){
int j = nums.size() - 1;
while(nums.at(i) >= nums.at(j)) j--;
swap(nums.at(i), nums.at(j));
}
// after swapping, reverse the numbers after our current number at position i
reverse(nums.begin() + i + 1, nums.end());
}
};
Solution in Java Programming
class Solution {
public void swap(int A[],int i,int j){
int temp=A[i];
A[i]=A[j];
A[j]=temp;
}
public void nextPermutation(int[] a) {
if(a == null || a.length == 0) return;
int i = a.length-2;
while(i>=0 && a[i] >= a[i+1]) i--;
if(i >=0 ){
int j=a.length-1;
while(a[j] <= a[i]) j--;
swap(a, i, j);
}
reverse(a, i+1, a.length-1);
}
public void reverse(int A[],int i,int j){
while(i<j) swap(A, i++, j--);
}
}Solution in Python Programming
class Solution(object):
def nextPermutation(self, nums):
l=len(nums)-2
r=len(nums)-1
c=0
while l>=0 and len(nums)>1:
if nums[l]>=nums[r]:
l-=1
r-=1
else:
t=min([x for x in nums[l+1:] if x>nums[l]])
ind=[x for x in nums[l+1:]].index(t)+l+1
y=nums[l]
nums[l]=nums[ind]
nums[ind]=y
temp=nums[r:]
temp.sort()
for i in range(len(temp)):
nums[r+i]=temp[i]
l-=1
r-=1
c=+1
break
if c==0:
nums.reverse()Solution in C# Programming
public class Solution {
public void NextPermutation(int[] nums) {
int length = nums.Count();
if(length<=1)
return;
var head=new BT();
head.num=nums[length-1];
int i;
for (i=length-2; i>=0; i--){
//for(int x=0;x<list.)
head.Insert(nums[i]);
var greater= head.FindGreaterNum(nums[i]);
//Console.WriteLine(greater);
if(greater!=null)
{
nums[i]=(int)greater;
break;
}
}
var list=new List<int>();
InorderTraverse(list,head);
for(int j=0;j<list.Count();j++)
{
nums[j+i+1]=list[j];
}
}
public void InorderTraverse(List<int> list, BT pointer)
{
if(pointer==null)
return;
InorderTraverse(list, pointer.left);
if(pointer.num!=null)
list.Add((int)pointer.num);
InorderTraverse(list, pointer.right);
}
}
public class BT{
public int? num;
public BT left;
public BT right;
public void Insert(int n){
var pointer=this;
var newnode= new BT();
newnode.num=n;
while(pointer!=null){
if(pointer.num==null || n <= pointer.num)
{
if(pointer.left==null)
{
pointer.left=newnode;
return;
}
pointer=pointer.left;
}
else{
if(pointer.right==null)
{
pointer.right=newnode;
return;
}
pointer=pointer.right;
}
}
}
public int? FindGreaterNum(int n)
{
var pointer=this;
while (pointer!=null)
{
if(pointer.num > n)
{
if(pointer.left == null || pointer.left.num <= n){
var result=pointer.num;
pointer.num=null;
return result;
}
else
pointer=pointer.left;
}
else
pointer=pointer.right;
}
return null;
}
}Also read,