[LintCode]繰り返し要素付き配列
10126 ワード
再帰的な実装:
非再帰的実装(nextPermutationベース):
1 class Solution {
2 public:
3 /**
4 * @param nums: A list of integers.
5 * @return: A list of unique permutations.
6 */
7 vector<vector<int> > permuteUnique(vector<int> &nums) {
8 // write your code here
9 sort(nums.begin(), nums.end());
10 vector<vector<int> > permutations;
11 if (nums.empty()) return permutations;
12 permutate(nums, 0, permutations);
13 return permutations;
14 }
15 private:
16 void permutate(vector<int> nums, int start, vector<vector<int> >& permutations) {
17 if (start == nums.size()) {
18 permutations.push_back(nums);
19 return;
20 }
21 for (int i = start; i < (int)nums.size(); i++) {
22 if (i == start || nums[i] != nums[start]) {
23 swap(nums[start], nums[i]);
24 permutate(nums, start + 1, permutations);
25 }
26 }
27 }
28 };
非再帰的実装(nextPermutationベース):
1 class Solution {
2 public:
3 /**
4 * @param nums: A list of integers.
5 * @return: A list of unique permutations.
6 */
7 vector<vector<int> > permuteUnique(vector<int> &nums) {
8 // write your code here
9 vector<vector<int> > permutations;
10 if (nums.empty()) return permutations;
11 vector<int> copy(nums.begin(), nums.end());
12 nextPermutation(nums);
13 permutations.push_back(nums);
14 while (nums != copy) {
15 nextPermutation(nums);
16 permutations.push_back(nums);
17 }
18 return permutations;
19 }
20 private:
21 void nextPermutation(vector<int>& nums) {
22 int k = -1, n = nums.size();
23 for (int i = n - 2; i >= 0; i--) {
24 if (nums[i] < nums[i + 1]) {
25 k = i;
26 break;
27 }
28 }
29 if (k == -1) {
30 reverse(nums.begin(), nums.end());
31 return;
32 }
33 int l;
34 for (int i = n - 1; i > k; i--) {
35 if (nums[i] > nums[k]) {
36 l = i;
37 break;
38 }
39 }
40 swap(nums[l], nums[k]);
41 reverse(nums.begin() + k + 1, nums.end());
42 }
43 };