首页 > 代码库 > 【LeetCode】Permutation全排列
【LeetCode】Permutation全排列
1. Next Permutation
实现C++的std::next_permutation函数,重新排列范围内的元素,返回按照 字典序 排列的下一个值较大的组合。若其已经是最大排列,则返回最小排列,即按升序重新排列元素。不能分配额外的内存空间。
void nextPermutation(vector<int>& nums) { next_permutation(nums.begin(), nums.end()); }
全排列 Permutation 问题已经被古人研究透了,参见 Wikipedia page,Next Permutation 有一个经典的简单有效算法,还能解决含有重复元素的全排列问题。
- 从尾端寻找第一个下标 i,使 nums[i] < nums[i + 1]。若这样的 i 不存在,则这个排列已经是降序排列(或者元素全部相同),那么直接逆序得到升序排列。
- 从尾端寻找第一个下标 j,使 nums[i] < nums[j]。若 i 存在,则 j 一定存在且 i < j,因为 j 起码可以 = i + 1。
- 交换 i 和 j 位置的元素。
- 逆序从 i + 1 到结尾的子数组,即求出下一个序列。
e.g.
nums = [6, 3, 4, 9, 8, 7, 1] i j
- 找到 i = 2,nums[i] = 4。i 右边的一定是降序排列 [9, 8, 7, 1]。
- 从尾端找第一个大于 nums[i] 的数 7,即 nums[j] = 7。
- 交换 4 和 7,[6, 3, 7, 9, 8, 4, 1]。保证交换后的 [6, 3, 7, ......] 一定大于原来的 [6, 3, 4, ......],且可以发现 i 右边的 [9, 8, 4, 1] 仍然是降序排列。
- 对 i 右边进行逆序,得到结果 [6, 3, 7, 1, 4, 8, 9]。
C++实现:
1 void nextPermutation(vector<int>& nums) { 2 int j = nums.size() - 1, i = j; 3 while (--i >= 0) { 4 if (nums[i] < nums[i + 1]) 5 break; 6 } 7 if (i != -1) { 8 while (j > i) { 9 if (nums[j] > nums[i]) 10 break; 11 j--; 12 } 13 swap(nums[i], nums[j]); 14 } 15 reverse(nums.begin() + i + 1, nums.end()); 16 return; 17 }
【LeetCode】Permutation全排列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。