《LeetCode 力扣》 - 1054. 距离相等的条形码 (哈希+计数+优先队列)

• ref
  • 1054. 距离相等的条形码
• contact
  • 每日一题

方法1 哈希计数+隔位插入

• 步骤
  • 1、哈希计数
  • 2、讲计数结果进行排序，出现次数多的放前面
  • 3、隔位插入，先出现次数多的，插入到偶数位置，然后再插入奇数位置
• 复杂度
  • 时间复杂度 O(klogk + n) （k为数的类型个数）
  • 空间复杂度 O(n)

class Solution {

    /**
     * @param Integer[] $barcodes
     * @return Integer[]
     */
    function rearrangeBarcodes($barcodes) {
        $size = count($barcodes);
        if($size <= 2) {
            return $barcodes;
        }
        $map = [];
        $result = array_fill(0, $size, 0);
        foreach($barcodes as $val) {
            $map[$val] = isset($map[$val]) ? ++$map[$val] : 1 ;
        }
        arsort($map);

        $index = 0;
        foreach($map as $item=>$count) {
            for($i = 0; $i < $count; $i++) {
                $result[$index] = $item;
                $index = $index + 2;
                if($index >= $size) {
                    $index = 1;
                }
            }
        }
        return $result;
    }
}

方法2 计数+排序重组+交叉插入

• 步骤
  • 1、计数
  • 2、将数组重排序，次数少的在前面，例如 [1,1,2] => [2,1,1]
  • 3、将数组从中间分开，然后进行交叉插入

class Solution {

    /**
     * @param Integer[] $barcodes
     * @return Integer[]
     */
    function rearrangeBarcodes($barcodes) {
        $size = count($barcodes);
        if($size <= 2) {
            return $barcodes;
        }

        $map = array_count_values($barcodes);
        usort($barcodes, function($a, $b) use ($map) {
            if($map[$a] == $map[$b]) {
                return $a - $b;
            } else {
                return $map[$a] - $map[$b];
            }
        });

        for($i = 0, $j = intval($size / 2), $k = 0; $i < $size; $i++) {
            if($i % 2 == 0) {
                $result[] = $barcodes[$j++];
            } else {
                $result[] = $barcodes[$k++];
            }
        }
        return $result;
    }
}

方法3 优先队列+依次插入

• 步骤
  • 1、哈希计数
  • 2、使用优先队列存储
  • 3、遍历优先队列，取次数最多的插入，然后取第二次数多的插入

class Solution {

    /**
     * @param Integer[] $barcodes
     * @return Integer[]
     */
    function rearrangeBarcodes($barcodes) {
        $size = count($barcodes);
        if($size <= 2) {
            return $barcodes;
        }
        $result = [];
        $map = array_count_values($barcodes);
        $pq = new SplPriorityQueue();
        $pq->setExtractFlags(SplPriorityQueue::EXTR_BOTH);
        foreach($map as $item=>$count) {
            $pq->insert($item, $count);
        }

        while(!$pq->isEmpty()) {
            $top = $pq->extract();
            $item = $top['data'];
            $count = $top['priority'];
            if(empty($result) || end($result) != $item) {
                $result[] = $item;
                if($count > 1) {
                    $pq->insert($item, --$count);
                }
            } else {
                $top2 = $pq->extract();
                $item2 = $top2['data'];
                $count2 = $top2['priority'];

                $result[] = $item2;
                $pq->insert($item, $count);

                if($count2 > 1) {
                    $pq->insert($item2, --$count2);
                }
            }
        }
        return $result;
    }
}

本作品采用《CC 协议》，转载必须注明作者和本文链接