Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public void nextPermutation(int[] nums) {
- int i = -1;
- // 1. find last increasing pair
- for (int j = 0; j < nums.length - 1; j++) {
- if (nums[j] < nums[j + 1]) {
- i = j;
- }
- }
- if (i == -1) {
- reverse(nums, 0);
- return;
- }
- // 2. from i + 1, find last k, that nums[k] > nums[i];
- int k = i + 1;
- for (int j = i + 1; j < nums.length; j++) {
- if (nums[j] > nums[i]) {
- k = j;
- }
- }
- swap(nums, i, k);
- // 3. reverse from i + 1 to end
- reverse(nums, i + 1);
- }
- void swap(int[] nums, int i, int j) {
- int tmp = nums[i];
- nums[i] = nums[j];
- nums[j] = tmp;
- }
- void reverse(int[] nums, int start) {
- int i = start, j = nums.length - 1;
- while (i < j) {
- swap(nums, i++, j--);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement