【每日一题Day166】LC1053交换一次的先前排列 | 贪心
交换一次的先前排列【LC1053】
给你一个正整数数组
arr
(可能存在重复的元素),请你返回可在 一次交换(交换两数字arr[i]
和arr[j]
的位置)后得到的、按字典序排列小于arr
的最大排列。如果无法这么操作,就请返回原数组。
虽然写出来了,但是花了55分钟…
还是有思路但是思路不清晰,然后直接敲代码,改来改去,老毛病了
笔试绝对ggg
看了别人的贪心,感觉自己笨笨的
-
思路:贪心
假设交换的左边元素为 a r r [ i ] arr[i] arr[i],右边的元素为 a r r [ j ] arr[j] arr[j]
-
怎样交换一次可以使字典序减小?
交换元素 a r r [ i ] > a r r [ j ] arr[i]>arr[j] arr[i]>arr[j]时,可以使字典序较小,所以数组必须是非递增的
-
如何使字典序小于原数组的情况下最大?【贪心】
保留前面高位部分的数组,尽可能交换低位部分的数组,即尽可能最小化 j j j的同时,最大化 i i i
枚举每个右端点,此时的右端点 r r r必须小于等于 n u m s [ j ] nums[j] nums[j],找到在 [ i , r − 1 ] [i,r-1] [i,r−1]范围内,从右往左第一个大于其的左端点进行交换
- 如果 a r r [ r ] > a r r [ j ] arr[r] > arr[j] arr[r]>arr[j], 那么从右往左第一个大于 a r r [ r ] arr[r] arr[r]的左端点一定在i的左边包括i,那么我们无法获得比目前的排列更大的排列
- 如果 a r r [ r ] = = a r r [ j ] arr[r] == arr[j] arr[r]==arr[j], 那么从右往左第一个大于 a r r [ r ] arr[r] arr[r]的左端点还是为 i i i,只需要修改右端点
- 如果 a r r [ r ] < a r r [ j ] arr[r] < arr[j] arr[r]<arr[j], 那么 l l l需要在 [ i + 1 , r − 1 ] [i+1,r-1] [i+1,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需要在[i+1,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 ( n 2 ) O(n^2) O(n2)
- 空间复杂度: O ( 1 ) O(1) O(1)
- 复杂度
-
别人的贪心
我们先从右到左遍历数组,找到第一个满足 a r r [ i − 1 ] > a r r [ i ] arr[i−1]>arr[i] arr[i−1]>arr[i]的下标 i i i,此时 a r r [ i − 1 ] arr[i−1] arr[i−1]就是我们要交换的数字,我们再从右到左遍历数组,找到第一个满足 a r r [ j ] < a r r [ i − 1 ] arr[j]<arr[i−1] arr[j]<arr[i−1] 且 a r r [ j ] ≠ a r r [ j − 1 ] arr[j] \neq arr[j - 1] arr[j]=arr[j−1] 的下标j,此时我们交换 a r r [ i − 1 ] arr[i−1] arr[i−1] 和 a r r [ 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)