有没有什么方法可以在O(n)中的C/C++中删除数组中的重复元素？假设元素是结果,a[5]={1,2,2,3,4}
那么数组应该包含{1,2,3,4}
解决方案可以使用两个for循环实现,但我相信这将是O(n ^ 2).
如果且仅当源数组已排序时,可以在线性时间内完成:
std::unique(a, a + 5); //Returns a pointer to the new logical end of a.
否则你必须先排序,这是(99.999%的时间)n lg n.
最好的情况是O(n log n).在原始数组上执行堆排序:O(n log n)及时,O(1)在空间中就地.然后按顺序运行数组,使用2个索引(source&dest)来折叠重复.这有副作用,不保留原始顺序,但由于"删除重复"没有指定要删除的重复项(第一个？第二个？最后一个？),我希望您不关心订单是否丢失.
如果您确实想要保留原始订单,则无法就地执行操作.但是如果你在原始数组中创建指向元素的指针数组,在指针上完成所有工作,并使用它们在最后折叠原始数组,这是微不足道的.
任何声称可以在O(n)时间和地点完成任何事情的人都是错误的,模仿一些关于什么O(n)和就地意味着什么的争论.一个明显的伪解决方案,如果你的元素是32位整数,就是使用一个初始化为全零的4千兆比特数组(大小为512兆字节),当你看到这个数字并翻过它时翻转一下这个位已经开启了.当然,你正在利用n一个由常数限制的事实,所以从技术上讲,一切都O(1)只有一个可怕的常数因素.但是,我确实提到过这种方法,因为如果n有一个小常量限制 - 例如,如果你有16位整数 - 这是一个非常实用的解决方案.
| 归档时间： |
|
| 查看次数： |
9036 次 |
| 最近记录： |