Permutation类

Next Permutation

先从后往前扫，如果nums[i] < nums[i + 1]的话，说明在i这个index上，可以通过与后面的数交换，得到一个更大的permutation。然后从array的最后一个往前找，找到第一个比nums[i]大的数，把这个数值交换，然后reverse从i + 1到最后一位的subarray。

public class Solution {
    public void nextPermutation(int[] nums) {
        if  (nums == null || nums.length <= 1) {
            return;
        }

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

        if (index == -1) {
            reverse(nums, 0, nums.length - 1);
            return;
        }

        int firstBig = index + 1;
        for (int i = nums.length - 1; i >= index + 1; i--) {
            if (nums[i] > nums[index]) {
                firstBig = i;
                break;
            }
        }

        swap(nums, index, firstBig);
        reverse(nums, index + 1, nums.length - 1);
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private void reverse(int[] nums, int i, int j) {
        while (i < j) {
            swap(nums, i++, j--);
        }
    }
}

Previous Permutation

跟上一题一样。

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A list of integers that's previous permuation
     */
    public ArrayList<Integer> previousPermuation(ArrayList<Integer> nums) {
        if (nums == null || nums.size() <= 1) {
            return nums;
        }

        int index = -1;
        for (int i = nums.size() - 2; i >= 0; i--) {
            if (nums.get(i) > nums.get(i + 1)) {
                index = i;
                break;
            }
        }

        if (index == -1) {
            reverse(nums, 0, nums.size() - 1);
            return nums;
        }

        int firstSmall = index + 1;
        for (int i = nums.size() - 1; i >= index + 1; i--) {
            if (nums.get(index) > nums.get(i)) {
                firstSmall = i;
                break;
            }
        }

        swap(nums, index, firstSmall);
        reverse(nums, index + 1, nums.size() - 1);
        return nums;
    }

    private void swap(ArrayList<Integer> nums, int i, int j) {
        int temp = nums.get(i);
        nums.set(i, nums.get(j));
        nums.set(j, temp);
    }

    private void reverse(ArrayList<Integer> nums, int i, int j) {
        while (i < j) {
            swap(nums, i++, j--);
        }
    }
}

Permutation Sequence

public class Solution {
    public String getPermutation(int n, int k) {
        if (n == 0 || k == 0) {
            return "";
        }

        int[] factorial = new int[n + 1];
        factorial[0] = 1;
        List<Integer> numbers = new ArrayList<Integer>();

        for (int i = 1; i <= n; i++) {
            factorial[i] = factorial[i - 1] * i;
            numbers.add(i);
        }

        --k;
        StringBuffer sb = new StringBuffer();
        for (int i = 1; i <= n; i++) {
            int fact = factorial[n - i];
            int index = k / fact;
            sb.append(numbers.get(index));
            numbers.remove(index);
            k %= fact;
        }
        return sb.toString();
    }
}

Permutation Index

public class Solution {
    /**
     * @param A an integer array
     * @return a long integer
     */
    public long permutationIndex(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }

        int n = A.length;
        long[] factorial = new long[n];
        factorial[0] = 1;
        for (int i = 1; i < n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }

        long result = 0;
        for (int i = 0; i < A.length; i++) {
            int rank = 0;
            for (int j = i + 1; j < A.length; j++) {
                if (A[i] > A[j]) {
                    rank++;
                }
            }
            result += rank * factorial[n - i - 1];
        }
        return result + 1;
    }
}

Permutation Index II