arrays - 相邻掉期的最小数量

Question

这是在线笔试的问题之一。

编号为 (1...N) 的书籍已到达仓库。

如果书“i”仅出现在书“i+1”的左侧（对于所有 i，1 <= i <= N-1）并且书 N 出现在书 1 的左边。[是的！任何循环排序的序列都是最佳排列]

收到的书是随机顺序的。现在你的任务是找出实现上述最佳排列所需的最少移动次数。

请注意，唯一有效的移动是选择一对相邻的书并让它们交换位置。

例如，如果书籍最初的顺序是 3 5 4 2 1

解决办法可以

一个。首先交换第二对书： { result : 3 4 5 2 1 }

湾。交换最右边的一对：{ result : 3 4 5 1 2 }

因此，在 2 步中，我们实现了最佳安排。

我尝试但无法找到解决方案。首先我将数组分成两个数组，然后我将对两个数组应用插入排序，但这也不起作用。请帮我找出这个问题的算法。

score 1 · Accepted Answer

N,1 可以是序列中的任何位置。例如 1..5，可以是 3,4,5,1,2。所以第一个数字可能是 1..5，即比Previous question复杂 5 倍。所以，你必须做5次。使用具有可替换比较功能的排序算法。

因此，对于第三次测试，比较将是：-

// returns <0, 0 or >0
int compare(a,b){
     return ((b+N-3)%N) - ((a+N-3)%N);
}

1 回答 1