lc1053. 交换一次的先前排列

题目链接:LC1053. 交换一次的先前排列

题解

第一次碰到num list 的字典序,数字大的字典序大。

题目合法交换就是去找一个逆序数,即 i<j, arr[i]>arr[j]。结合字典序最大条件,就是要 i 最大,i 最大情况下,还要 j 最大。这种方法的复杂度应该是 O(n2)O(n^2)

官方题解复杂度是 O(n)O(n),枚举 i: n-2 -> 0,有一个隐含的假设已经枚举过的 [i,n) 是非递减的。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
def prevPermOpt1(self, arr: List[int]) -> List[int]:
mp = {}
a = -1
b = -1
n = len(arr)
for i in range(n-1, -1, -1):
for j in range(i-1, -1, -1):
if j <= a:
break
if arr[j] > arr[i]:
a = j
b = i

if a == -1:
return arr
else:
for j in range(a, b):
if arr[b] == arr[j]:
b = j
break
tmp = arr[a]
arr[a] = arr[b]
arr[b] = tmp
return arr

lc1053. 交换一次的先前排列

https://blog.xiang578.com/problem/lc1053.html

作者

Ryen Xiang

发布于

2023-04-03

更新于

2024-08-05

许可协议


网络回响

评论