767. Reorganize String

发表于 | 分类于 | 浏览 次

Reorganize String

Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.

If possible, output any possible result. If not possible, return the empty string.

Example 1:

1
2
Input: S = "aab"
Output: "aba"

Example 2:

1
2
Input: S = "aaab"
Output: ""

Note:

  • S will consist of lowercase letters and have length in range [1, 500].

解法1

根据插空法, 当数组中有n个数,且n/2个数都是同一个数.如下所示:

1
2
3
4
5
6
7
示例1
[1,1,1,2,2]
1,2,1,2,1

示例2
[1,1,1,2,2,2]
1,2,1,2,1,2

则数组中最多有(n+1)/2个是同一个数,这样可以通过插空法,隔一个位置插一个数保证每两个相邻的数不同.
如示例1中如果1的个数再多出一个就无法保证每两个相邻的数不同.

因为通过首先统计数组中是否存在出现次数超过(n+1)/2的数来判断是否存在一种方案能保证任意两个相邻的数不同.
然后通过重组数组来给出一种方案.重组数组的过程中,首先将数组中元素按出现次数由少到多排序,然后,将前面一般分布到奇数位置上,将后一般分布到偶数位置上来实现任意两个相邻的元素不同.

c++如何对map进行排序

时间复杂度为O(m(n + logn)),其中n是S的长度,m是用于统计每个字符出现次数的map的大小.因此时间复杂度为O(n)
空间复杂度为O(n+m)

解法2

https://leetcode.com/articles/reorganized-string/