有没有可能解决这个问题，解决方案的时间复杂度比线性更好？

N根灯泡通过导线连接。每个灯泡都有一个与之相关的开关，但由于接线错误，开关也会将所有灯泡的状态改变到当前灯泡的右侧。给定所有灯泡的初始状态，找到开启所有灯泡所需按下的最小开关数量。您可以多次按下相同的开关。

注意：0代表灯泡关闭，1代表灯泡开启。

输入：[0 1 0 1]

步骤：

press switch 0 : [1 0 1 0] 
press switch 1 : [1 1 0 1] 
press switch 2 : [1 1 1 0] 
press switch 3 : [1 1 1 1]

回程：4

2017-05-06 Aleph_0

如果您的输入是一个固定宽度的整数存储的位矢量，是的。否则，你将如何避免迭代整个数组？ – Veedrac

我同意不可能比线性时间做得更好 –

我能想到的一个提高速度的方法就是将序列化把所有的灯泡放在右边。特别是GPU可能能够有效地做到这一点（我不确定，因为您需要更改每个循环都会生效的元素）。

也许使它成为一个合适的布尔数组，并按位XOR模式到阵列上？

除非真正的过程比XOR-boolean值更复杂，否则内存速度将成为瓶颈 - 而不是CPU时间。除非是纯粹的学术目的，否则性能咆哮适用： http://ericlippert.com/2012/12/17/performance-rant/

2017-05-07 01:27:50 Christopher

回答