难度: Medium
Submission
运行时间: 47 ms
内存: 28.7 MB
class Solution:
def minimumSwaps(self, nums: List[int]) -> int:
mi,mx=nums[0],nums[0]
n=len(nums)
idx1,idx2=0,0
for i in range(1,n):
if nums[i]<mi:
mi=nums[i]
idx1=i
if nums[i]>=mx:
mx=nums[i]
idx2=i
return idx1+n-1-idx2 if idx1<=idx2 else idx1+n-1-idx2-1
Explain
这个解法首先遍历一次数组，找出数组中的最小值和最大值以及它们的索引。最小值的索引记为 idx1，最大值的索引记为 idx2。这个解法的关键在于通过计算最小值和最大值的位置来确定最少的交换次数：1. 如果最小值在最大值之前出现（idx1 <= idx2），则直接计算两者到其应在的位置的距离差，即 idx1 (最小值移动到数组起始位置) 和 n-1-idx2 (最大值移动到数组末尾位置)。2. 如果最小值在最大值之后出现（idx1 > idx2），需要额外减去1，因为当最小值向前移动时，最大值的位置也会随之前移。这种情况下，我们在计算最大值移动到末尾的距离时多算了一次。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def minimumSwaps(self, nums: List[int]) -> int:
mi, mx = nums[0], nums[0] # 初始化最小值和最大值为数组的第一个元素
n = len(nums) # 数组长度
idx1, idx2 = 0, 0 # 最小值和最大值的索引
for i in range(1, n): # 遍历数组
if nums[i] < mi:
mi = nums[i] # 更新最小值
idx1 = i # 更新最小值索引
if nums[i] >= mx:
mx = nums[i] # 更新最大值
idx2 = i # 更新最大值索引
# 计算最少交换次数
if idx1 <= idx2:
return idx1 + n - 1 - idx2 # 最小值在最大值前面
else:
return idx1 + n - 1 - idx2 - 1 # 最小值在最大值后面，减1考虑到交叉影响
Explore
在最小值在最大值后面的情况下，当最小值向数组的起始位置移动时，如果不减去1，则会重复计算最大值的位置移动。因为在将最小值向前移动过程中，最大值的索引会因为数组的改变而自动向前移动一位，所以在计算最大值向数组末尾移动的距离时，应该减去这个已经因最小值移动而产生的一次位移，以避免重复计数。
在遍历数组时，如果遇到值等于当前最小值的情况，通常保持最小值的索引为首次出现的位置，因为这有助于减少总的交换次数，即尽可能保持最小值靠近开始位置。对于最大值，选择`>=`而不是`>`是为了在遇到相同的最大值时更新索引到最后出现的位置，这样可以减少最大值向数组末尾移动的距离，从而可能减少总的交换次数。
这种方法在计算时确实考虑了数组中可能存在的重复元素，因为它通过更新最小值和最大值的索引来应对重复出现的情况。重复元素本身不会影响结果的正确性，因为算法在考虑最少交换次数时已经考虑到了最小值和最大值可能多次出现的情形。
如果数组已经是按照最小值到最大值排序的，则最小值的索引为0，最大值的索引为数组长度减一。根据算法逻辑，这种情况下返回的交换次数将是0，这是正确的结果，因为已排序数组不需要任何交换。因此，这个算法在这种情况下仍然有效并且能够返回正确的交换次数。