多维数组重复 - 性能

Question

检查多维数组是否包含2个或更多相等值并且仅返回第一个数据的最佳方法是什么.

例如:我有一系列包含的人

[0][firstName] = 'John';
[0][lastName]  = 'Doe';

[N][firstName] = 'Marco';
[N][lastName]  = 'Polo';

[120][firstName] = 'John';
[120][lastName]  = 'Doe';

应该检测到索引120是重复的并将其删除.

我正在寻找最佳性能,我不想在数组上循环并检查每次是否有值.

有更快的东西吗？

Answer 1

它是元素清晰度问题,基本上是O(NlogN)通过排序和迭代(排序后,重复将彼此相邻 - 这样很容易检测到它们)

但是,通过在迭代时将所有元素存储到哈希表中,并且如果元素已经存在则中断,它也可以O(N) 平均地并且通过O(N)额外的空间来完成.

如果稍后需要它,您可能还希望存储每个元素的原始索引(并且不要将索引用作键).

伪代码:

map <- empty hash map
for each element e with idx i in list (in ascending order of i):
     if (map.contains(e)):
           e is a dupe, the first element is in index map.get(e)        
     else:    
           map.add(e,i)