难度: Hard
Submission
运行时间: 143 ms
内存: 28.1 MB
class Solution(object):
def sortArray(self, nums):
n = len(nums)
p = [0] * n
ans1 = 0
for i in range(n):
if p[i] == 0:
p[i] = 1
j = i
next_j = nums[j]
if next_j == j:
continue
count = 1
while next_j != i:
j = next_j
p[j] = 1
next_j = nums[j]
count += 1
if i == 0:
ans1 += count - 1
else:
ans1 += count + 1
p = [0] * n
ans2 = 0
for i in range(n - 1, -1, -1):
if p[i] == 0:
p[i] = 1
j = i
next_j = (nums[j] - 1) % n
if next_j == j:
continue
count = 1
while next_j != i:
j = next_j
p[j] = 1
next_j = (nums[j] - 1) % n
count += 1
if i == n - 1:
ans2 += count - 1
else:
ans2 += count + 1
return min(ans1, ans2)
Explain
这个题解试图通过两种策略来最小化移动数组元素到正确位置所需的步数。第一种策略是直接按照每个元素的目标位置进行排序，尝试发现和纠正位置错误的元素，从而形成一个闭环。第二种策略是考虑元素可能向左移动的情况，也形成闭环。具体步骤包括：检查每个元素是否已经在正确位置上；如果不在，则通过循环跟踪每个元素应该在的位置，直到循环回到起点；计算每个闭环中移动的次数。最终返回两种策略中最小的移动次数。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution(object):
def sortArray(self, nums):
n = len(nums)
p = [0] * n # 用于跟踪每个位置的元素是否已经在正确位置
ans1 = 0 # 第一种策略的最小移动次数
for i in range(n):
if p[i] == 0: # 如果当前元素未处理
p[i] = 1 # 标记为已处理
j = i
next_j = nums[j] # 下一个需要检查的位置
if next_j == j:
continue
count = 1 # 用于计算闭环中的移动次数
while next_j != i: # 继续循环直到回到起点
j = next_j
p[j] = 1
next_j = nums[j]
count += 1
if i == 0:
ans1 += count - 1
else:
ans1 += count + 1
p = [0] * n # 重新初始化 p 用于第二种策略
ans2 = 0 # 第二种策略的最小移动次数
for i in range(n - 1, -1, -1):
if p[i] == 0: # 如果当前元素未处理
p[i] = 1
j = i
next_j = (nums[j] - 1) % n
if next_j == j:
continue
count = 1
while next_j != i:
j = next_j
p[j] = 1
next_j = (nums[j] - 1) % n
count += 1
if i == n - 1:
ans2 += count - 1
else:
ans2 += count + 1
return min(ans1, ans2) # 返回两种策略的最小值
Explore
在第一种策略中，如果一个元素已经位于其正确的位置，即数组索引与元素值相等，这意味着这个位置上的元素不需要移动。因此，我们可以将其标记为已处理并跳过，这样做可以避免不必要的操作，减少计算量。此外，跳过已正确放置的元素也可以防止形成只有一个元素的闭环，从而简化问题处理。
第二种策略考虑了元素可能需要向左移动的情况。使用 `(nums[j] - 1) % n` 的计算方式基于假设数组中的元素应该位于 `nums[j] - 1` 的位置，即元素值减1后的位置（考虑元素值与索引的对应关系）。模运算 `% n` 确保索引值在数组的有效范围内，特别是当 `nums[j] - 1` 为负数时，模运算可以正确地将索引环绕到数组的末尾。这种计算方式允许我们在数组中循环定位每个元素应放置的正确位置。
在代码中，通过使用一个辅助数组 `p` 来跟踪每个元素的处理状态，确保每个元素只被处理一次。在开始处理每个元素之前，首先检查其对应的 `p` 值是否为0（未处理）。如果已经标记为处理（`p[i]` 不为0），则直接跳过该元素，从而避免重复处理已经在正确位置的元素。这种方法确保每个元素只在它首次被发现不在正确位置时被移动，有效避免了重复和不必要的操作。
在代码中，闭环的移动次数计算基于闭环内的元素个数。对于每个闭环，我们通过循环跟踪元素位置，直到回到闭环的起点，计算过程中每一次跳转都增加1到移动次数。特别地，如果闭环的起始点是数组的第一个元素或最后一个元素，移动次数的计算稍有不同，以适应数组边界的特殊情况。对于起始点为0的情况，因为第一个元素的位置通常是移动的起始点，所以移动次数是闭环长度减1。而对于起始点为数组最后一个元素的情况，由于可能需要额外的一步将元素移回起点，因此移动次数是闭环长度加1。这种计算确保了考虑到数组边界和元素的实际移动需求。