leetcode/31.next-permutation.cpp at master · 9sheng/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
/**
 * 31. Next Permutation

 * Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
 *
 * If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
 *
 * The replacement must be in-place and use only constant extra memory.
 *
 * Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
 *
 * 1,2,3 → 1,3,2
 * 3,2,1 → 1,2,3
 * 1,1,5 → 1,5,1
 */

#include "testharness.h"
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

class Solution {
 public:
  void nextPermutation(vector<int>& nums) {
    int ti = -1;
    int tj = -1;
    int v = -1;
    // From right to left, i.e., for i = nums.size() .. 1,
    // find largest nums[j] such that j > i and nums[i] > nums[j].
    // If we find nums[j], we swap nums[i] and num[j], and sort nums[j:]
    for (int i = nums.size() - 1; i >= 0; i--) {
      for (int j = i + 1; j < nums.size(); j++) {
        if (nums[i] < nums[j] && (v == -1 || v > nums[j])) {
          ti = i;
          tj = j;
          v = nums[j];
        }
      }
      if (ti != -1) {
        int tmp = nums[ti];
        nums[ti] = nums[tj];
        nums[tj] = tmp;
        sort(&nums[ti+1], &nums[nums.size()]);
        return;
      }
    }

    sort(nums.begin(), nums.end());
  }
};

TEST(Solution, test) {
  vector<int> nums{1,2,3};
  nextPermutation(nums);
  ASSERT_EQ(nums[0], 1);
  ASSERT_EQ(nums[1], 3);
  ASSERT_EQ(nums[2], 2);
}

TEST(Solution, test2) {
  vector<int> nums{3,2,1};
  nextPermutation(nums);
  ASSERT_EQ(nums[0], 1);
  ASSERT_EQ(nums[1], 2);
  ASSERT_EQ(nums[2], 3);
}

TEST(Solution, test3) {
  vector<int> nums{1,1,5};
  nextPermutation(nums);
  ASSERT_EQ(nums[0], 1);
  ASSERT_EQ(nums[1], 5);
  ASSERT_EQ(nums[2], 1);
}

TEST(Solution, test4) {
  vector<int> nums{1,3,2};
  nextPermutation(nums);
  ASSERT_EQ(nums[0], 2);
  ASSERT_EQ(nums[1], 1);
  ASSERT_EQ(nums[2], 3);
}

TEST(Solution, test5) {
  vector<int> nums{4,2,0,2,3,2,0};
  nextPermutation(nums);
  ASSERT_EQ(nums[0], 4);
  ASSERT_EQ(nums[1], 2);
  ASSERT_EQ(nums[2], 0);
  ASSERT_EQ(nums[3], 3);
  ASSERT_EQ(nums[4], 0);
  ASSERT_EQ(nums[5], 2);
  ASSERT_EQ(nums[6], 2);
}