高效排序排列
高效排序排列
提问于 2014-12-21 00:23:24
给定n的未排序排列，我希望通过从左到右迭代来收集数字，以便对预排列(1...n)进行排序。
为了达到这个目标，我需要做多少次迭代？
例如：
给定'3，7，4，2，10，8，9，1，6，5'-迭代次数为6。
在第一次迭代中，我将收集数字1
在第二次迭代中，我将收集数字2
在第三次迭代中，我将收集数字3、4、5
在第四次迭代中，我将收集数字6
在第五次迭代中，我将收集数字7、8、9
在第六次迭代中，我将收集数字10
我构建了一个简单的代码，使用O(n^2)完成任务，但我需要它更有效率，所以我认为这里有一个我遗漏的技巧。
有什么建议吗？
Stack Overflow用户
发布于 2014-12-21 00:43:39
因为你已经知道了结果，所以我不清楚你是在什么意义上对任何东西进行“排序”。您在寻找什么结果--关于在每次迭代中“收集”哪些数字的信息，如您在Q中所示？在本例中，这里有一个简单的Python 2实现示例：
target = 3, 7, 4, 2, 10, 8, 9, 1, 6, 5
def do_permut(targ):
look_for = 1
iter_num = 1
while look_for != len(targ) + 1:
print 'Iteration', iter_num, ':',
for item in targ:
if item == look_for:
print item,
look_for += 1
print
iter_num += 1
do_permut(target)然而，任务不可避免地是O(N平方) --记住，大O代表最坏的情况！您将在N个数字上进行最多N次迭代(最坏的情况是在开始对targ进行反向排序时) --因此，N的平方。您可以通过收集之前在迭代过程中看到的一组数字并在look_for在该集合中时中断，对每次迭代进行轻微的optimize，但这只(大致)使每次迭代的工作量减半，因此它仍然是O(N平方)。
如果您能更好地解释您希望从您的工作中获得什么结果和输出，我们可能会提供更多帮助！
出于好奇，这里有一个具有上述“改进”的版本，并且还进行了健全性检查，以确保它会引发异常，而不是永远循环，如果传递的序列不是[1:n)的排列...：
target = 3, 7, 4, 2, 10, 8, 9, 1, 6, 5
def do_permut(targ):
look_for = 1
iter_num = 1
while look_for != len(targ) + 1:
print 'iteration', iter_num, ':',
seen = set()
found_in_iter = 0
for item in targ:
seen.add(item)
if item == look_for:
print item,
found_in_iter += 1
look_for += 1
if look_for in seen:
break
print
if not found_in_iter:
raise ValueError('missing: %s' % look_for)
iter_num += 1
do_permut(target)页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/27582089
复制相关文章
相似问题
腾讯云开发者
