专业的外贸行业网站制作,网站编程技术 吉林出版集团股份有限公司,旅游网站建设初衷,上海专业网站推广公司文章目录 1. 题目2.分析3.解答3.1 先排序#xff0c;后交换3.2 先交换#xff0c;后排序 1. 题目
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
例如#xff0c;arr [1,2,3] #xff0c;以下这些都可以视作 arr 的排列#xff1a;[1,2,3]、[1,3,2]、[3… 文章目录 1. 题目2.分析3.解答3.1 先排序后交换3.2 先交换后排序 1. 题目
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
例如arr [1,2,3] 以下这些都可以视作 arr 的排列[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地如果数组的所有排列根据其字典顺序从小到大排列在一个容器中那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列那么这个数组必须重排为字典序最小的排列即其元素按升序排列。
例如arr [1,2,3] 的下一个排列是 [1,3,2] 。类似地arr [2,3,1] 的下一个排列是 [3,1,2] 。而 arr [3,2,1] 的下一个排列是 [1,2,3] 因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums 找出 nums 的下一个排列。
必须 原地 修改只允许使用额外常数空间。
2.分析
这里需要找下一个字典序更大的排列那么意味着要从数组的后端入手。如果最后两个元素原本就是升序的那么就直接交换这两个元素就好了这个组合即使下一个更大的组合。 但是如果这两个元素不是升序的那么交换这两个元素反而导致拍列更小。因此必须要找到从后向前数的第一个升序排列的两个相邻元素。找到之后交换这两个元素即可。 但是交换后的元素依然不一定是下一个更大排列组合。如[5,7,6,4]这个排列交换5和7得到的是[7,5,6,4]这个组合显然不是下一个更大排列毕竟手动排列组合一下发现下一个组合应该是[6,4,5,7]
那么应该是考虑从后向前第一个升序段的后一个元素开始将后面所有的元素按字典排序然后找到紧挨着升序点前一个元素的那个元素将其交换即可。 或者找到紧挨着升序段前一个元素的数据将其进行交换然后将从升序段后一个元素开始的数据按字典方式排序。
3.解答
3.1 先排序后交换
public class Solution {public void nextPermutation(int[] nums) {if (nums.length 1) return;int len nums.length;for (int i len - 1; i 0;i--) {if (nums[i] nums[i - 1]) {Arrays.sort(nums, i, len);for (int j i; j len; j) {if (nums[j] nums[i - 1]) {int temp nums[j];nums[j] nums[i - 1];nums[i - 1] temp;return;}}}}Arrays.sort(nums);}
}3.2 先交换后排序
public class Soultion {public void nextPermutation(int[] nums) {if (nums.length 1) return;int i nums.length - 2;int j nums.length - 1;int k nums.length - 1;while (i 0 nums[i] nums[j]) {i--;j--;} if (i 0) {while (nums[i] num[k]) {k--;}swap(nums, i, k);}Arrays.sort(nums, j, nums.length);}private void swap(int[], int i, int k) {int temp nums[i];nums[i] nums[k];nums[k] temp;}
}
