在二维数组中删除重复行

Question

我从之前的帖子中得到了一些想法，他们谈论如何为每个$arr[$i]创建一个哈希值，然后比较哈希值来获取唯一的数组，但我不知道具体该怎么做。

我的示例数组数据：

$arr = [
    [0, 1, 2, 3],
    [4, 5, 2, 1],
    [0, 0, 0, 0],
    [0, 1, 2, 3]
];

我期望返回：

[
    [0, 1, 2, 3],
    [4, 5, 2, 1],
    [0, 0, 0, 0]
]

- Jay

Answer 1

快速简单：

$arr = array_map('unserialize', array_unique(array_map('serialize', $arr)));

- Alix Axel

---

这种方法并不完美，因为如果条目的顺序不同，它将无法捕获重复项，例如 serialize(['a' => ['b' => 1], 'c' => ['d' => 2]]),serialize(['c' => ['d' => 2], 'a' => ['b' => 1]])。 - Gajus

@GajusKuizinas：无论如何，这些都不是PHP数组定义的相同之处：http://codepad.org/nsTS5bDc。但是，如果这正是您想要的，请事先使用适当的排序函数。 - Alix Axel

顺便问一下，为什么你在使用(un)serialize？除非我弄错了，json_encode/json_decode 会更快。 - Gajus

@GajusKuizinas：当我写这个的时候，它运行得非常慢（我认为现在更快了）。无论如何，还有其他原因，因为JSON不能理解所有PHP类型。 - Alix Axel

如果序列化和反序列化的速度小于遍历数组的速度，并且速度很重要，那么这是一个天才的想法。 - Ajayi Oluwaseun Emmanuel

Answer 2

PHP已经提供了一种本地方法来直接删除数组中的重复行。

在array_unique()调用中传递SORT_REGULAR标志，告诉PHP在评估值时不改变数据类型。

代码: (演示)

var_export(array_unique($arr, SORT_REGULAR));

- mickmackusa

Answer 3

foreach($arr as $key => $value)
{
   foreach($arr as $key2 => $value2)
   {
      if($value2 == $value && $key != $key2)
       {
          unset($arr[$key]);
       }
    }
}

这不是最优雅的方法，但它确实可以做到你需要的事情。问题在于你不能递归使用array_unique。

这是另一种方法，来自于PHP.net文档注释（里面有很棒的代码片段）

function arrayUnique($myArray) 
{ 
    if(!is_array($myArray)) 
           return $myArray; 

    foreach ($myArray as &$myvalue){ 
        $myvalue=serialize($myvalue); 
    } 

    $myArray=array_unique($myArray); 

    foreach ($myArray as &$myvalue){ 
        $myvalue=unserialize($myvalue); 
    } 

    return $myArray; 

} 

- Tyler Carter

Answer 4

这里还有一个想法。虽然并不是非常优雅，但可能相当快。它类似于Chacha102的第二部分，但如果子数组中只有整数值，则速度会更快。

// implode the sub arrays
$tmpArray = array();
foreach ($arr as $key => $array) {
    $tmpArray[$key] = implode(',', $array);
}

// get only the unique values
$tmpArray = array_unique($tmpArray);

// explode the values
$arr = array();
foreach ($tmpArray as $key => $string) {
    $arr[$key] = explode(',', $string);
}

- Darryl Hein

Answer 5

哈希是一个好主意，平均情况下可以将解决方案的时间复杂度降为O(n)。

基本上，你需要遍历一遍数组$arr并且对整个数组进行哈希处理，然后将其与之前看到的哈希进行比较（使用isset()实际上是O(1)，或者更精确地说是O(m)，其中m是内部数组中元素的数量）。如果出现哈希冲突，你需要比较实际的数组元素。通常情况下，哈希冲突意味着你之前已经看过这个数组，它是重复的，但这并不是绝对的。以下是一些伪代码PHP，实现了这种算法。

function mkhash($array = array()) {
   $hash = "";
   foreach ($array as $element) {
      $hash .= md5($element);
   }
}

$seen = array();
$newArray = array();
foreach($arr as $elementArray) {
   $hash = mkhash($elementArray); 
   if(!isset($seen[$hash])) {
     $newArray[] = $elementArray;
     $seen[$hash] = $elementArray;
   } else if(count(array_diff($elementArray, $seen[$hash])) > 0) {
      $newArray[] = $elementArray; //this is true if two different arrays hashed to the same element
   }
}

哈希方法实现起来比较困难，正确处理冲突也很棘手，因此时间复杂度为O(nlogn)。

使用O(nlogn)的方法是对数组进行排序。

$arr = array_multisort($arr); //O(nlogn)

然后你只需要比较相邻的数组是否重复即可。

当然，你也可以简单地使用O(n^2)的方法，将每个内部数组与其他每个内部数组进行比较...

编辑：哦，这里还有另一个O(n)的想法，你可以使用数组键递归地构建一棵trie树，使其映射到其他数组，因此你最终得到一个深度为m的数组，其中m是你拥有的最长内部数组。trie树的每个分支表示一个唯一的内部数组。当然，你需要编写一些额外的代码来将trie树转换回2D数组，因此在输入的基数非常大时才能看到性能优势！

- Charles Ma

Answer 6

这取决于您是否有足够的资源将较大的数组保留在内存中（基本上，这取决于您是否只想要唯一值以防止在循环期间膨胀，或者您只需要最终结果是一个唯一值的数组。

对于所有示例，我假设您正在从某些外部来源（如MySQL查询）获取要输入到大数组中的值。

为了防止重复项进入主数组：

您可以创建两个数组，一个带有字符串值，一个带有实际数组值。

while($row = $results->fetch_assoc) {
     $value_string = implode("," $row);
     if(in_array($value_string, $check_array) {
         $check_array[] = $value_string;
         $master_array[] = $row;
      }
 }

在上面的代码中，它只是判断您的数据集的字符串版本是否在已经迭代过的字符串数据集数组中。使用两个数组会增加一些额外开销，但是两个数组中都不会出现重复值。

另外，就像我之前提到的，还有一个名为array_unique的函数，它可以在所有数据输入后执行。修改上面的示例，您可以得到如下代码：

while($row = $results->fetch_assoc) {
     $master_array[] = $row;
   }
 $master_array = array_unique($master_array);

- Anthony