[LintCode] 반복 요소 정렬
10125 단어 code
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 };
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
소스 코드가 포함된 Python 프로젝트텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.