# share my O(n) time solution which beats 77.55 % of c submissions

• show the code first

``````void nextPermutation(int* nums, int numsSize)
{
int i, j;
int t = -1;
for (i = numsSize - 1; i > 0; --i) {
if (nums[i - 1] < nums[i]) {
t = i - 1;
break;
}
}
for (i = t + 1, j = numsSize - 1; i < j; ++i, --j) {
// reverse
nums[i] ^= nums[j];
nums[j] ^= nums[i];
nums[i] ^= nums[j];
}
if (t >= 0) {
for (i = t + 1; i < numsSize; ++i) {
if (nums[i] > nums[t]) {
nums[i] ^= nums[t];
nums[t] ^= nums[i];
nums[i] ^= nums[t];
break;
}
}
}
}
``````

my idea is:

1. Starts from the last element to find the one fitting nums[i-1]<nums[i], then nums[i-1] is the target digit to be changed to a bigger one, we mark "i - 1" as "t";
2. Because nums[t] is the first one fitting nums[i-1]<nums[i], those digits in larger indexes fit nums[i-1]>nums[i]. we want the result as small as possible, and we know that we put the large digit in a higher index, the number is smaller, so we reverse sort the digits in higher indexes than t;
3. The last step, we find a smallest digit from indexes higher than t which's bigger than nums[t], and swap it with nums[t], finally we get the answer.

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