网站选项卡图标,怎么建自己的手机网站吗,建设网站的调研报告,广州建设信息网官网题目描述
整数数组的一个排列 就是将其所有成员以序列或线性顺序排列。 例如#xff0c;arr [1,2,3] #xff0c;以下这些都可以视作 arr 的排列#xff1a;[1,2,3]、[1,3,2]、[3,1,2]、[2,3,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 的下一个排列。
必须原地修改只允许使用额外常数空间。
示例1 输入nums [1,2,3] 输出[1,3,2] 示例2 输入nums [3,2,1] 输出[1,2,3] 示例3 输入nums [1,1,5] 输出[1,5,1] 解题思路 根据题目描述这里得到两个限制条件1在原来的基础上增加 2增加的要是最少 第一个条件将后面的大数和前面的小数进行交换即可增大数值。如13456将6和3交换就可以得到一个更大的数16453第二个条件交换的数尽可能的靠后如将5和6交换得到的数13465会比16453小。此外对第一个交换位置后的数字进行升序排列将大数往后移即可以得到更小的数值如将6和3进行交换后得到16453再将第一个交换位置6后面的数字进行升序排列得到16345会比原来大但是数值更小了。
故可以总结出算法这里就使用题解给出的算法
首先从后向前查找第一个顺序对 (i,i1)满足 a[i]a[i1]。这样「较小数」即为 a[i]。此时 [i1,n)必然是下降序列。如果找到了顺序对那么在区间 [i1,n)中从后向前查找第一个元素 j 满足a[i]a[j]。这样「较大数」即为 a[j]。交换 a[i]与 a[j]此时可以证明区间 [i1,n)必为降序。我们可以直接使用双指针反转区间 [i1,n)使其变为升序而无需对该区间进行排序。
拿一个序列举例 输入[5, 4, 7, 5, 3, 2] 输出[5, 5, 2, 3, 4, 7] 首先从后往前找到第一个元素使a[i]a[i1],即为4定位较小数 然后从后往前找到第一个元素使a[j]a[i],即为5定位较大数 将较小数和较大数进行交换得到5,5,7,4,3,2 对较小数位置后面的数进行升序排列得到552347即为最终答案 代码
class Solution {public void nextPermutation(int[] nums) {// 判断是否使降序数组降序数组直接返回升序结果int flag 0;for(int i 0;i nums.length-1; i){if(nums[i] nums[i1]){flag 1;break;}}if(flag 0){// 若数组是完全降序排列则变为升序即可Arrays.sort(nums);}else{int p 0, q 0;// 找到较小数for(q nums.length-2; q 0; q --)if(nums[q] nums[q1])break;// 找到较大数for(p nums.length-1; p q; p --)if(nums[q] nums[p])break;// 交换两个数swap(nums, p, q);// 将较小数索引后面的数按升序排列因为是降序排列所以只需要逆置即可reverse(nums, q1);}}public void swap(int[] nums, int i, int j) {int temp nums[i];nums[i] nums[j];nums[j] temp;}public void reverse(int[] nums, int start) {int left start, right nums.length - 1;while (left right) {swap(nums, left, right);left;right--;}}
}
