31. Next Permutation
2022/2/4 6:42:23
本文主要是介绍31. Next Permutation,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Take the following nums as an exmpel : [2,4,3,1]
The 4, 3, 1 is a decending order, it cannot be larger any more. How we can make 2,4,3,1 larger? we need to find a number in 4,3,1, which is just larger than 2, as 4,3,1 is decending order, so we check from back to front, when we arrive "3", we know it is the the number that we want to find.
Then replace "2" with "3", the nums become 3, 4, 2, 1, we need to reverse 4,2,1 to make it 3,1,2,4, that is the result.
public void nextPermutation(int[] nums) { int index = 0; for (int i = nums.length-1; i > 0; i--) { if (nums[i] > nums[i - 1]) { index = i; break; } } if(index>0) for (int i = nums.length - 1; i >= index; i--) { if (nums[i] > nums[index-1]) { swap(nums, index-1, i); break; } } reverse(nums, index); } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } private void reverse(int[] nums, int index) { int i = index, j = nums.length - 1; while (i < j) { swap(nums, i++, j--); } }
What if the problem is find the Last Permutation? for example [3,1,2,4]
The 1, 2, 4 is a ascending order, it cannot be smaller any more. How can we make 3,1,2,4 smaller? we need to find a number in 1,2,4, which is just smaller than 3, as 1,2,4 is ascending order, so we check from back to front, when we arrive "2", we know it is the number that we want to find.
Then replace "3" with "2", the nums become 2, 1,3,4, we need to reverse 1,3,4 to make it 2,4,3,1, that is the result!
public void nextPermutation(int[] nums) { int index = 0; for (int i = nums.length-1; i > 0; i--) { if (nums[i] < nums[i - 1]) { //here ">" become "<" index = i; break; } } if(index>0) for (int i = nums.length - 1; i >= index; i--) { if (nums[i] < nums[index-1]) { //here ">" become "<" swap(nums, index-1, i); break; } } reverse(nums, index); } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } private void reverse(int[] nums, int index) { int i = index, j = nums.length - 1; while (i < j) { swap(nums, i++, j--); } }
这篇关于31. Next Permutation的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南