1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int minimumSwaps(int[] nums) {
int minIdx = 0, maxIdx = 0, max = nums[0], min = nums[0];
for (int i = 0; i < nums.length; i++) {
if (nums[i] >= max) {
max = nums[i];
maxIdx = i;
} else if (nums[i] < min) {
min = nums[i];
minIdx = i;
}
}
return minIdx <= maxIdx ? minIdx - 0 + nums.length - 1 - maxIdx : minIdx + nums.length - 1 - maxIdx - 1;
}
}
|
我们找到最靠左的最小值, 以及最靠右的最大值. 然后看最小值的index是否比最大值的index小, 如果是, 那么两个数字各自swap各自的. 如果最大值的index比最小值的index小, 那么最小值swap到最左边的时候, 最大值会往右swap一格, 我们再把最大值swap到最右边的时候可以少swap一次.
时间复杂度: O(n)
空间复杂度: O(1)
