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


  • 0
    T

    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.

Log in to reply
 

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