4mS C solution with comments


  • 1
    M

    Primary challenge here is to identify the pattern, probably the easiest way to figure that out is to try numerous different use cases.

    Here we are essentially looking for the next lexicographically greater arrangement, which means that a number at a more significant offset should be replaced with a higher value from a less significant location.

    Consider the example {4,2,0,2,3,2,0}: Solution to this would be {4, 2, 0, 3, 0, 2, 2}, we have replaced 2 at the more significant offset 3 with value 3 from the offset 4. Searching for this value which needs to be replaced can be done using the following loop:

        /* Seek the first offset where a number is preceded by a smaller
        value */
        for (i = len - 1; i >= 0; --i)
        {
            /* Break if the present offset value is smaller than the
            largest one till now */
            if (nums[i] < nums[g])
                break;
    
            /* If needed, update the largest value */
            if (nums[g] < nums[i])
                g = i;
        }
    

    Basically we are scanning the array in reverse looking for a value which is smaller than the largest encountered value. Once we locate the more significant offset which needs to be replaced, we need to next find the replacement, the less significant location.

             /* Locate the smallest value within the range [i, len] which is
                greater than the value at i */
                for (j = i + 1; j < len; ++j)
                {
                    /* If needed, update the offset */
                    if ((nums[j] > nums[i]) &&
                        ((nums[j] - nums[i]) < (nums[g] - nums[i])))
                        g = j;
        
                    /* If the difference is one, then break */
                    if (nums[g] - nums[i] == 1)
                        break;
                }
        
                /* Swap the values, and sort the rest of the array */
                swap_ints(&nums[i], &nums[g]);
    

    Above loop locates that less significant location of the next greater number. Final step would be swap the values and then to sort the array. Main function is given below, full source code can be accessed from Bit Bucket link . As you can see, the overall complexity would be O(nLog(n)).

    /***********************************************************************/
    /* 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, do not allocate 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                                                       */
    /***********************************************************************/
    void nextPermutation(int* nums, int numsSize)
    {
        int i, j, g = numsSize - 1;
        int len = numsSize;
    
        /* Maintain Sanity */
        if (!nums || !numsSize)
            return;
    
        /* Array length has to be greater than one */
        if (len <= 1)
            return;
    
        /* Seek the first offset where a number is preceded by a smaller
        value */
        for (i = len - 1; i >= 0; --i)
        {
            /* Break if the present offset value is smaller than the
            largest one till now */
            if (nums[i] < nums[g])
                break;
    
            /* If needed, update the largest value */
            if (nums[g] < nums[i])
                g = i;
        }
    
        /* If the array is sorted in decreasing order, then simply reverse */
        if (i < 0)
            reverse_arr(nums, len);
    
        /* Else we need to seek the pairs to swap */
        else
        {
            /* Locate the smallest value within the range [i, len] which is
            greater than the value at i */
            for (j = i + 1; j < len; ++j)
            {
                /* If needed, update the offset */
                if ((nums[j] > nums[i]) &&
                    ((nums[j] - nums[i]) < (nums[g] - nums[i])))
                    g = j;
    
                /* If the difference is one, then break */
                if (nums[g] - nums[i] == 1)
                    break;
            }
    
            /* Swap the values, and sort the rest of the array */
            swap_ints(&nums[i], &nums[g]);
            quick_sort(nums, i + 1, len - 1);
        }
    }
    

Log in to reply
 

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