Reorganize String
|Last edited: 2024-5-20
ID
767
Data Type
Heap (Priority Queue)
Difficulty
Medium
Tags
Greedy
Counting Sort
URL
https://leetcode.com/problems/reorganize-string/description/
Completed Date
Preference
Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.
Return any possible rearrangement of s or return "" if not possible.
Example 1:
Example 2:
Constraints:
  • 1 <= s.length <= 500
  • s consists of lowercase English letters.

题解

这个题我一开始想的是abcabc这样排列，但是遇到 vvvlo 变 vlvov 就不行了，其实改下思路，把出现最多的字符先按ABABABAB这样的排法排出来，然后剩下的再按
主要是这个的优先队列法我不会，这个题作为这个分类的第一道题学习一下

优先队列

这个函数的实现基于最大堆（Max Heap）数据结构，使用了一种被称为优先队列（Priority Queue）的数据结构策略。
这个函数的实现分为以下几个步骤：
  1. 首先，函数创建了一个映射freq来存储每个字符及其出现的频率。这是通过遍历输入字符串s的每个字符并更新映射freq来实现的。
  1. 然后，函数创建了一个最大堆maxHeap，并将映射freq中的每个键值对（即字符及其出现的频率）作为一个结构体Set添加到最大堆中。这里，最大堆的比较函数是基于出现频率的，即出现频率更高的字符在最大堆中的位置更靠前。
  1. 接下来，函数开始从最大堆中取出字符并添加到结果字符串result中。首先，它检查最大堆是否为空，如果为空且previous不为空（即前一次从最大堆中取出的字符还有剩余），则返回一个空字符串，因为这种情况下无法重新组织字符串使得任意两个相邻的字符都不相同。然后，函数从最大堆中取出一个字符，将其添加到结果字符串result中，并将其出现的频率减一。如果previous不为空，那么将其添加回最大堆中。如果取出的字符的出现频率仍然大于零，那么将其保存在previous中。
  1. 最后，当最大堆为空且previous也为空时，函数返回结果字符串result。
这个函数的时间复杂度是O(n log n)，其中n是输入字符串s的长度。因为它需要遍历输入字符串一次来创建映射freq，然后在最大堆中插入和删除元素的时间复杂度都是O(log n)。这个函数的空间复杂度是O(n)，因为它需要存储输入字符串s的每个字符及其出现的频率，以及结果字符串result。

贪心

  1. 首先，函数创建了一个映射myMap来存储每个字符及其出现的频率。同时，它还记录了出现次数最多的字符maxOccurrenceChar和其出现次数maxOccurrence。如果有任何字符的出现次数超过了(len(s)+1)/2（即字符串长度的一半加一），那么函数会立即返回一个空字符串，因为这种情况下无法重新组织字符串使得任意两个相邻的字符都不相同。
  1. 然后，函数开始在结果字符串的偶数索引位置放置出现次数最多的字符。这是通过创建一个新的字符串数组result，然后在其偶数索引位置放置maxOccurrenceChar来实现的。每放置一个字符，maxOccurrence就会减一，直到maxOccurrence为零，此时将maxOccurrenceChar从映射中删除。
  1. 最后，函数将剩余的字符放置在result的剩余空位中。首先尝试填充偶数索引位置，然后填充奇数索引位置。这是通过遍历myMap中的每个键值对，然后在result中相应的位置放置键（即字符）来实现的。
函数的最后，使用strings.Join(result, "")将结果字符串数组result连接成一个字符串，并返回这个字符串。
这个函数的时间复杂度是O(n)，其中n是输入字符串s的长度。因为它需要遍历输入字符串两次：一次是在创建映射myMap时，一次是在创建结果字符串result时。这个函数的空间复杂度也是O(n)，因为它需要存储输入字符串s的每个字符及其出现的频率，以及结果字符串result。