g********r
发帖数: 58 | 1 不用 假定数组是1~n的某个排列
O(n) time + 常数 space 的解法 － 对吗？
int minSwap(int[] A) {
n = len(A)
idxMin = 0
valMin = A[idxMin]
for (int i = 0, i< n, i++)
if valMin > A[i]
valMin = A[i]
idxMin = i
if idxMin == n-1
return n-2
cnt = idxMin
leftMin = INT_MAX
for (int i = 0; i<= idxMin-1 ; i++)
if leftMin < A[i]
leftMin = A[i]
rightMin = A[n-1]
for (int i = n-1; i<= idxMin+1; i-- )
if A[i]> rightMin || A[i] ... 阅读全帖 |
|
