证明至少 1 和最多 2*k - 1 的反演被移除
我不明白“反转被删除”是什么意思，我不知道从哪里开始。
问问题
856 次
1 回答
3
如果列表是1, 3, 2, 4并且它已更改为，1, 2, 3, 4则您已删除反转。
显然，您已经删除了至少 1 个反转，因为a[i]并且a[i+k]出现了故障。最多您删除2*k - 1，因为如果a[i]大于a[i+1], ... ,a[i+k-1]然后您修复k-1反转。a[i+k]比它下面的所有都小也是如此。因此，您最多可以拥有k-1 + k-1 + 1（最后一个是我们已经数过的），它等于2k - 1
示例： ->用, ,1,10,3,4,5,6,7,8,9,2切换2 现在小于 10，并且 2 也小于 3-9 即 7 个数字。进一步的 10 现在大于 3-9，这又是 7 个数字，所以改进是a[2]a[10]k = 87 + 7 + 1 = 15 = 2*8 - 1
于 2012-11-04T03:16:30.823 回答