验证数组排序最小交换次数解法正确性的技术咨询

问题背景 #

给定一个包含n个不同元素的数组，找出将其排序所需的最小交换次数。示例如下：

• 输入{4, 3, 2, 1}，输出2
• 输入{1, 5, 4, 3, 2}，输出2

我的解法思路 #

我想到的解法步骤是：

1. 先对原数组进行排序，这一步的时间复杂度是O(n logn)
2. 用哈希表记录已经处理过的元素，对比原数组和排序后数组的对应位置元素，跟踪需要的交换操作，这一步时间复杂度O(n)
   整体的总时间复杂度为O(n logn)

实现代码 #

def solution(array)
 sorted = array.sort
 puts array.inspect
 puts sorted.inspect
 counter_parts_that_have_been_seen = {}
 number_of_swaps_required = 0
 array.each_with_index do | val, idx |
 if counter_parts_that_have_been_seen[val] == true
 next
 end
 array_val = val
 sorted_val = sorted[idx]
 if array_val != sorted_val
 puts "A swap will be required: array val is #{array_val} and sorted_array_val is #{sorted_val}"
 number_of_swaps_required += 1
 counter_parts_that_have_been_seen[sorted_val] = true
 end
 end
 puts "Number of swaps required are: #{number_of_swaps_required}"
end

我的困惑 #

我现在没法确定这个解法是否正确，想请教各位大佬：怎么验证这个解法的正确性呢？

内容的提问来源于stack exchange，提问作者Khoj Badami