商城网站建设定制网站建设,网站配图尺寸,营销外贸网站建设,网站开发环境分析交换一次的先前排列【LC1053】 给你一个正整数数组 arr#xff08;可能存在重复的元素#xff09;#xff0c;请你返回可在 一次交换#xff08;交换两数字 arr[i] 和 arr[j] 的位置#xff09;后得到的、按字典序排列小于 arr 的最大排列。 如果无法这么操作#xff0c;…交换一次的先前排列【LC1053】 给你一个正整数数组 arr可能存在重复的元素请你返回可在 一次交换交换两数字 arr[i] 和 arr[j] 的位置后得到的、按字典序排列小于 arr 的最大排列。 如果无法这么操作就请返回原数组。 虽然写出来了但是花了55分钟… 还是有思路但是思路不清晰然后直接敲代码改来改去老毛病了 笔试绝对ggg 看了别人的贪心感觉自己笨笨的 思路贪心 假设交换的左边元素为arr[i]arr[i]arr[i]右边的元素为arr[j]arr[j]arr[j] 怎样交换一次可以使字典序减小 交换元素arr[i]arr[j]arr[i]arr[j]arr[i]arr[j]时可以使字典序较小所以数组必须是非递增的 如何使字典序小于原数组的情况下最大【贪心】 保留前面高位部分的数组尽可能交换低位部分的数组即尽可能最小化jjj的同时最大化iii 枚举每个右端点此时的右端点rrr必须小于等于nums[j]nums[j]nums[j]找到在[i,r−1][i,r-1][i,r−1]范围内从右往左第一个大于其的左端点进行交换 如果arr[r]arr[j]arr[r] arr[j]arr[r]arr[j], 那么从右往左第一个大于arr[r]arr[r]arr[r]的左端点一定在i的左边包括i那么我们无法获得比目前的排列更大的排列如果arr[r]arr[j]arr[r] arr[j]arr[r]arr[j], 那么从右往左第一个大于arr[r]arr[r]arr[r]的左端点还是为iii只需要修改右端点如果arr[r]arr[j]arr[r] arr[j]arr[r]arr[j], 那么lll需要在[i1,r−1][i1,r-1][i1,r−1]的范围内才可能是字典序增大 实现 class Solution {public int[] prevPermOpt1(int[] arr) {int n arr.length;int l 0;// 升序数组本身就是最小排列while (l n - 1 arr[l] arr[l 1]){l;}if (l n - 1) return arr; // 升序数组// 非升序数组 枚举每个右端点 找到从右往左第一个大于其的左端点进行交换// 之后交换的右端点必须小于等于arr[j]并且左端点l必须大于i才能使交换结果变小// 如果arr[r] arr[j], 那么从右往左第一个大于arr[r]的左端点一定在i的左边包括i那么我们无法获得比目前的排列更大的排列// 如果arr[r] arr[j], 那么从右往左第一个大于arr[r]的左端点还是为i只需要修改右端点// 如果arr[r] arr[j], 那么l需要在[i1,r-1]的范围内才可能是字典序增大int i -1, j -1;// 记录最终的交换结果for (int r n - 1; r i; r--){if (j ! -1 arr[r] arr[j]) continue;if (j ! -1 arr[r] arr[j]) {j r;continue;}for (l r - 1; l (i ! -1 ? i 1 : 0); l--){if (arr[l] arr[r]){i l;j r;break;}}}// 交换int tmp arr[i];arr[i] arr[j];arr[j] tmp;return arr;}
}复杂度 时间复杂度O(n2)O(n^2)O(n2)空间复杂度O(1)O(1)O(1) 别人的贪心 我们先从右到左遍历数组找到第一个满足 arr[i−1]arr[i]arr[i−1]arr[i]arr[i−1]arr[i]的下标 iii此时 arr[i−1]arr[i−1]arr[i−1]就是我们要交换的数字我们再从右到左遍历数组找到第一个满足 arr[j]arr[i−1]arr[j]arr[i−1]arr[j]arr[i−1] 且 arr[j]≠arr[j−1]arr[j] \neq arr[j - 1]arr[j]arr[j−1] 的下标 j此时我们交换 arr[i−1]arr[i−1]arr[i−1] 和 arr[j]arr[j]arr[j] 后返回即可。
class Solution {public int[] prevPermOpt1(int[] arr) {int n arr.length;for (int i n - 1; i 0; --i) {if (arr[i - 1] arr[i]) {for (int j n - 1; j i - 1; --j) {if (arr[j] arr[i - 1] arr[j] ! arr[j - 1]) {int t arr[i - 1];arr[i - 1] arr[j];arr[j] t;return arr;}}}}return arr;}
}作者ylb
链接https://leetcode.cn/problems/previous-permutation-with-one-swap/solutions/2205403/python3javacgotypescript-yi-ti-yi-jie-ta-pxxt/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。复杂度 时间复杂度O(n)O(n)O(n)空间复杂度O(1)O(1)O(1)
