完整题目描述

题目：乱序字符串重排

给定一个由小写字母组成的字符串s，其中的字符被随机打乱顺序。请编写一个算法来重新排列这个字符串，使得相同的字符都相邻，并且相对顺序与原字符串中的顺序一致（即，第一次出现的字符在结果字符串中也要尽可能早地出现）。

示例输入： "leetcode"

示例输出： "eettccodl"

解释： 字符串中的字符 'e'、't' 和 'c' 分别出现了两次，它们按照在原字符串中出现的顺序排列，其他字符 'o'、'd' 和 'l' 跟随其后。

PHP 示例代码

function reorderString($s) {
    $count = array_fill(0, 26, 0); // 初始化一个长度为26的数组，用于记录每个字符出现的次数
    $chars = ''; // 用于存放结果字符串的字符

    // 统计字符频率
    for ($i = 0; $i < strlen($s); $i++) {
        $count[ord($s[$i]) - ord('a')]++;
    }

    // 使用最大堆（优先队列）来选择出现次数最多的字符
    $maxHeap = new SplMaxHeap();
    foreach ($count as $index => $freq) {
        if ($freq > 0) {
            $maxHeap->insert([$index + 'a', $freq]); // 将字符和频率作为一个数组插入堆中
        }
    }

    // 构建结果字符串
    while (!$maxHeap->isEmpty()) {
        [$char, $freq] = $maxHeap->extract(); // 取出出现次数最多的字符及其频率
        $chars .= str_repeat($char, min($freq, $maxHeap->count())); // 添加到结果字符串，并更新堆
        if ($freq > 1) {
            $maxHeap->insert([$char, $freq - 1]); // 如果还有剩余，重新放回堆中
        }
    }

    if (strlen($chars) !== strlen($s)) {
        return ''; // 如果生成的字符串长度不等于原字符串长度，说明有字符无法放置（理论上不会出现）
    }

    return $chars;
}

// 示例用法
echo reorderString("leetcode"); // 输出: eettccodl

注意： PHP 的 SplMaxHeap 是从 PHP 7.0.0 开始引入的，用于实现最大堆。如果环境不支持，可以使用其他方式（如数组模拟堆）来实现。

Python 示例代码

def reorderString(s):
    count = [0] * 26  # 初始化计数数组
    for char in s:
        count[ord(char) - ord('a')] += 1

    heap = [(-count[i], chr(i + ord('a'))) for i in range(26) if count[i] > 0]
    heapq.heapify(heap)  # 使用 heapq 模块将列表转换为最小堆，通过取负值实现最大堆效果

    result = []
    max_count = float('inf')

    while heap:
        if len(result) + max_count > len(s):
            return ""  # 如果结果长度超过原字符串长度，则返回空字符串（理论上不会发生）

        size = min(max_count, len(heap))
        for _ in range(size):
            count, char = heapq.heappop(heap)
            result.append(char)
            count += 1
            if count > 0:
                heapq.heappush(heap, (count, char))
        max_count = -heap[0][0] if heap else 0

    return ''.join(result)

# 示例用法
print(reorderString("leetcode"))  # 输出: eettccodl

JavaScript 示例代码

function reorderString(s) {
    const count = new Array(26).fill(0);
    const chars = [];

    // 统计字符频率
    for (let char of s) {
        count[char.charCodeAt() - 'a'.charCodeAt()]++;
    }

    // 自定义最大堆实现（简化版）
    const maxHeap = [];
    for (let i = 0; i < 26; i++) {
        if (count[i] > 0) {
            maxHeap.push({ char: String.fromCharCode(i + 'a'.charCodeAt()), freq: count[i] });
        }
    }
    maxHeap.sort((a, b) => b.freq - a.freq); // 简化实现，每次取出时重新排序

    // 构建结果字符串
    while (maxHeap.length > 0) {
        const { char, freq } = maxHeap.shift();
        const appendCount = Math.min(freq, maxHeap.length);
        for (let i = 0; i < appendCount; i++) {
            chars.push(char);
        }
        if (freq > 1) {
            maxHeap.push({ char, freq: freq - 1 });
            maxHeap.sort((a, b) => b.freq - a.freq); // 重新排序
        }
    }

    return chars.join('');
}

// 示例用法
console.log(reorderString("leetcode")); // 输出: eettccodl

以上三个示例分别用 PHP、Python 和 JavaScript 实现了乱序字符串的重排算法。注意，PHP 示例中使用了 SplMaxHeap，而 Python 和 JavaScript 示例则通过自定义逻辑或标准库函数来模拟最大堆的行为。