LeetCode 31. Next Permutation

Divide Two Integers.

The procedure to make the next permutation:

  1. Find the last number that smaller than its next number. If you can not find it, then the next permutation will be the first permutation.
  2. Find the last number that larger than the number you found in Step 1.
  3. Swap the number you found in Step 1 and Step 2.
  4. Sort (Reverse should be enough) the number after the position you found in Step 1.
public class Solution {
    public void NextPermutation(int[] nums) {
        int pos1 = -1;
        for (int i = nums.Length-1; i > 0; i--){
            if(nums[i] > nums[i-1]) {
                pos1 = i-1;
                break;
            }
        }
        if (pos1 == -1){
            Array.Reverse(nums);
            return;
        }
        for (int i = nums.Length-1; i > 0; i--){
            if(nums[pos1] < nums[i]){
                int t = nums[pos1];
                nums[pos1] = nums[i];
                nums[i] = t;
                Array.Reverse(nums, pos1+1, nums.Length - pos1 - 1);
                break;
            }
        }
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *