Java&Go-LeetCode31. 下一个排列-奥里给

• 算法
  • 1.首先找到最大的i使得nums[i]<nums[i+1]
  • 2.如果没有这样的i，当前排列是字典序最大的排列，翻转整个数组即是下一个排列
  • 3.如果找到这样的i，接着找到最大的j使得nums[j]>nums[i]
  • 4.交换i和j，再翻转数组的[i+1, n-1]部分即是下一个排列

public void nextPermutation(int[] nums) {
    int n = nums.length;
    int i = 0;
    for (i = n - 2; i >= 0; i--) {
        if (nums[i] < nums[i+1]) {
            break;
        }
    }

    if (i < 0) {
        reverse(nums, 0, n-1);
    } else {
        int j = 0;
        for (j = n - 1; j > i; j--) {
            if (nums[j] > nums[i]) {
                break;
            }
        }
        swap(nums, i, j);
        reverse(nums, i + 1, n - 1);
    }
}

private void swap(int[] nums, int x, int y) {
    int temp = nums[x];
    nums[x] = nums[y];
    nums[y] = temp;
}

private void reverse(int[] nums, int start, int end) {
    for (int i = start, j = end; i < j; i++, j--) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

func nextPermutation(nums []int)  {
    n := len(nums)
    i := 0
    for i = n - 2; i >= 0; i-- {
        if nums[i] < nums[i+1] {
            break;
        }
    }

    if i < 0 {
        reverse(nums, 0, n-1)
    } else {
        j := 0
        for j = n - 1; j > i; j-- {
            if nums[j] > nums[i] {
                break;
            }
        }
        nums[i], nums[j] = nums[j], nums[i]
        reverse(nums, i+1, n-1)
    }
}

func reverse(nums []int, start, end int) {
    for i, j := start, end; i < j; i += 1 {
        nums[i], nums[j] = nums[j], nums[i]
        j--
    }
}