Next Permutation

1package pkg5leetcode.top100;2 3/*4 * Next Permutation | LC 315 * APPROACH: Find pivot, swap with rightmost larger, reverse suffix.6 * COMPLEXITY: Time O(n), Space O(1)7 */8public class top100_LC31NextPermutation {9    static void nextPermutation(int[] nums) {10        int i = nums.length - 2;11        while (i >= 0 && nums[i] >= nums[i + 1]) i--;12        if (i >= 0) {13            int j = nums.length - 1;14            while (nums[j] <= nums[i]) j--;15            swap(nums, i, j);16        }17        reverse(nums, i + 1, nums.length - 1);18    }19 20    static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }21 22    static void reverse(int[] a, int lo, int hi) {23        while (lo < hi) swap(a, lo++, hi--);24    }25 26    public static void main(String[] args) {27        int[] a = {1, 2, 3};28        nextPermutation(a);29        check(java.util.Arrays.equals(a, new int[]{1, 3, 2}), "case1");30        int[] b = {3, 2, 1};31        nextPermutation(b);32        check(java.util.Arrays.equals(b, new int[]{1, 2, 3}), "case2");33        System.out.println("all tests passed");34    }35 36    static void check(boolean cond, String name) {37        if (!cond) throw new AssertionError("FAILED: " + name);38        System.out.println("  PASS " + name);39    }40}