1

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

例如：我有一组人，其中包含

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

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

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

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

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

有什么更快的吗？

4

2 回答 2

6

这是元素差异性问题，基本上是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)
于 2012-12-12T12:16:01.560 回答
1

你可以试试

// Generate Possible name with duplicate
$names = array("John","Doe","Polo","Marco","Smith");
$array = array();

for($i = 0; $i < 20; $i ++) {
    $key = mt_rand(0, 1000);
    $array[$key]["firstName"] = $names[array_rand($names)];
    $array[$key]["lastName"] = $names[array_rand($names)];
}

// Start Sorting process
ksort($array);

// Start Storage
$data = $hash = array();

// Loop and porpulate new array
foreach ( $array as $k => $v ) {
    $h = sha1($v['firstName'] . $v["lastName"]);
    isset($hash[$h]) or $data[$k] = $v and $hash[$h] = 1;
}

var_dump($data);
于 2012-12-12T13:12:37.453 回答