PHP数组 - 分离相同的值

Question

有没有好的或标准的方法来做这件事？

以以下示例为例：

$values = array(
    'blue'
    , 'blue'    
    , 'blue'
    , 'blue'
    , 'green'
    , 'red'
    , 'yellow'
    , 'yellow'
     , 'purple'
    , 'purple'
    , 'purple'
);

我需要它被分离开，使得没有两个相同的值相邻（除非没有可能的解决方案 - 在这种情况下，生成错误、返回false或其他任何结果都是可以接受的）。

这是我手动完成的上述数组，但我正在尝试更改它：

$values = array(
    'blue'
    , 'purple'
    , 'green'
    , 'purple'
    , 'blue'
    , 'red'
    , 'blue'
    , 'yellow'
    , 'blue'
    , 'yellow'
    , 'purple'
)

一开始，这些值不一定按顺序排列 -- 这只是为了简单起见。

有什么想法吗？有没有代码可以让我朝正确的方向迈进？

- Kerry Jones

Answer 1

这个函数应该可以解决问题：

function uniq_sort($arr){
    if(!count($arr))
        return array();

    $counts = array_count_values($arr);
    arsort($counts);
    while(NULL !== ($key = key($counts)) && $counts[$key]){
        if(isset($prev) && $prev == $key){
            next($counts);
            $key = key($counts);
            if($key === NULL)
                return false;
        }
        $prev = $result[] = $key;

        $counts[$key]--;
        if(!$counts[$key])
            unset($counts[$key]);

        arsort($counts);
        reset($counts);
    }
    return $result;
}

使用示例:

$values = array('blue', 'blue', 'blue', 'blue', 'green', 'red', 'yellow', 'yellow', 'purple', 'purple', 'purple');
print_r(uniq_sort($values));

$values = array('a', 'b', 'b');
print_r(uniq_sort($values));

$values = array(1);
print_r(uniq_sort($values));

$values = array(1, 1, 1, 1, 2, 3, 4);
print_r(uniq_sort($values));

$values = array(1, 1, 1, 1, 2, 3);
var_dump(uniq_sort($values));

并输出：

Array
(
    [0] => blue
    [1] => purple
    [2] => blue
    [3] => yellow
    [4] => blue
    [5] => purple
    [6] => blue
    [7] => purple
    [8] => red
    [9] => yellow
    [10] => green
)
Array
(
    [0] => b
    [1] => a
    [2] => b
)
Array
(
    [0] => 1
)
Array
(
    [0] => 1
    [1] => 3
    [2] => 1
    [3] => 4
    [4] => 1
    [5] => 2
    [6] => 1
)
bool(false)

- Paul

---

@Kerry 没问题，我收回我在原始修订中关于通过从循环中删除 arsort 可以进行优化的说法。事实证明，在 PHP 数组中交换两个键/值对的位置非常困难，而解决方案可能比调用 arsort 更慢。 - Paul

很好 - 在我看来，它是那些我今天之前从未想过需要的函数之一。 - Kerry Jones

不错。我觉得使用的方法（始终选择最高频率）如果存在解决方案，则保证找到解决方案。 - goat

Answer 2

逻辑：

先打印第一个值，再打印下一个值之前，将其与前一个值进行比较，如果它们相同，则跳过下一个值，以此类推。

- Kleber S.

---

如果最终有三个相同的，就像上面的例子一样呢？ - Kerry Jones

['a','b','b']会发生什么？我认为这个不适用。 - Matt Dodge

@KleberS 但是 ['b','a','b'] 是该列表的一个有效解决方案，而您的算法返回 false。这个（很可能是家庭作业）问题的关键是，您需要按最常见的元素首先对元素进行排序。 - Matt Dodge

@mattedgod -- 这绝对不是作业，这是另一家公司交给我的工作，虽然我有一个可行的解决方案，但它并不美观，我正在寻找一个更好的解决方案。我提供了一个样本数组 -- 希望我能将这个问题的答案应用到多维数组中。 - Kerry Jones

@Kerry 哈哈，我只是开玩笑说作业的事情。如果是一个没有声望的人问这个问题，我会更加怀疑。这让我想起了大学里那些“有趣”的算法问题。话虽如此，我认为wecsam的答案中的排序附加功能是你最好的选择。 - Matt Dodge

Answer 3

$values = array(
        'blue'
        , 'blue'    
        , 'blue'
        , 'blue'
        , 'green'
        , 'red'
        , 'yellow'
        , 'yellow'
        , 'purple'
        , 'purple'
        , 'purple'
    );
    $value_count = Array();
    foreach($values as $v){
        if(isset($value_count[$v])){
            $value_count[$v]++;
        }else{
            $value_count[$v] = 1;
        }
    }
    unset($v);
    //Now generate new array 
    $result = Array();//This line is technically not necessary 
    $done = false;
    while(!$done){
        $done = true;
        foreach($value_count as $k => &$c){
            if($c > 0){
                $result[] = $k;
                $c--;
                $done = false;
            }
        }
    }
    print_r($result);

这将导致以下结果：

Array
(
    [0] => blue
    [1] => green
    [2] => red
    [3] => yellow
    [4] => purple
    [5] => blue
    [6] => yellow
    [7] => purple
    [8] => blue
    [9] => purple
    [10] => blue
)

- wecsam

---

这并不真正起作用。它适用于示例输入数组，但对许多其他数组无效。比如 [1, 1, 1, 1, 2, 3, 4]。一个解决方案是 [1, 2, 1, 3, 1, 4, 1]，但您的代码返回了 [1, 2, 3, 4, 1, 1, 1]，这是不正确的。 - Paul

ASCII-lime说得对。然而，我认为在计算完计数之后按值计数降序排序，应该可以正常工作。基本上，从具有最高计数的元素开始填充结果数组。 - Matt Dodge

@mattedgod 是的，那应该可以。你还应该跟踪先前添加的值，如果具有最高计数的值与先前的值相同，则使用具有第二高计数的值。如果你遇到只剩一个唯一元素且它也是你的先前元素的情况，则返回 false。 - Paul

另外，顺便提一下：我认为只要一个元素从未出现超过（n+1）/2次，就会始终存在有效的解决方案。 - Matt Dodge

@Ascii-lime -- 你能展示一下更新后的代码吗？我正在尝试让它在一个多维数组和一个关联数组的数组中工作。 - Kerry Jones

Answer 4

遍历数组，记住你看到的最后一个值，如果匹配，则丢弃你正在查看的值。这里有一个例子：

$values = array(
    'blue'
    , 'blue'    
    , 'blue'
    , 'blue'
    , 'green'
    , 'red'
    , 'yellow'
    , 'yellow'
     , 'purple'
    , 'purple'
    , 'purple'
);

$last_seen_value = NULL;
foreach ($values as $i => $value) {
  if (0 == strcmp($value, $last_seen_value)) {
    unset($values[$i]);
  } else {
    $last_seen_value = $value;
  }
}

print_r($values);

# Output:
# 
# Array
# (
#     [0] => blue
#     [4] => green
#     [5] => red
#     [6] => yellow
#     [8] => purple
# )

- sczizzo

---

这将仅输出唯一的值。我认为OP想要的是数组“洗牌”，以便没有两个相同的值相邻。换句话说，输出数组应与输入数组的大小相同。 - Matt Dodge