2

我遇到了一个算法问题，要在 O(nlogn) 时间内找出数组中反转对的数量。我得到了解决方案。但是，我的问题是这个问题在现实生活中的应用是什么？就像我想知道一些我们需要知道反转对的应用程序。

4

2 回答 2

2

一个例子是十五谜题。如果你想随机打乱一个数字网格，你能一眼看出是否

1 14  5  _
7  3  2 12
6  9 13 15
4 10  8 11

是否可以通过滑动来解决？排列的奇偶性会告诉你它不是。

于 2010-09-23T14:19:24.373 回答
0

这是在现实生活中使用反转计数..假设您想知道两个列表的相似程度..基于排名..在任何电影网站上..比较两个电影的愿望清单，其中相似的很少显示给有相同选择的用户。

同样的逻辑适用于任何购物网站上的购物清单..根据他的活动推荐购物项目..

于 2012-09-17T19:50:16.940 回答