SHARE
TWEET

Untitled

a guest Sep 16th, 2019 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. https://leetcode.com/problems/permutations/
  3. Runtime: 40 ms, faster than 5.01% of Java online submissions for Permutations.
  4. Memory Usage: 36.8 MB, less than 97.16% of Java online submissions for Permutations.
  5. */
  6. class Solution {
  7.     public List<List<Integer>> permute(int[] nums) {
  8.         ArrayList<List<Integer>> output = new ArrayList<>();
  9.         for (int step = 0, il = factorial(nums.length); step < il; step++) {
  10.             output.add(Arrays.stream(nums).boxed().collect(Collectors.toList()));
  11.  
  12.             int i = nums.length - 2;
  13.             while (i > -1 && nums[i] >= nums[i + 1]) {
  14.                 --i;
  15.             }
  16.             if (i > -1) {
  17.                 int j = i + 1;
  18.                 while (j < nums.length && nums[i] < nums[j]) {
  19.                     ++j;
  20.                 }
  21.                 swap(nums, i, j - 1);
  22.             }
  23.             for (int s = i + 1, e = nums.length - 1; s < e; ++s, --e) {
  24.                 swap(nums, s, e);
  25.             }
  26.         }
  27.         return output;
  28.     }
  29.  
  30.     static int factorial(int n) {
  31.         int result = 1;
  32.         for (int i = 1; i <= n; i++) {
  33.             result *= i;
  34.         }
  35.         return result;
  36.     }
  37.  
  38.     public static void swap(int[] array, int i, int j) {
  39.         int temp = array[i];
  40.         array[i] = array[j];
  41.         array[j] = temp;
  42.     }
  43. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top