将字符串中的字符组合在一起的算法

Question

我正在寻找一种将字符串中的字符组合在一起的算法。例如：

如果我们有这个字符串：

ghfgjggjhfjfjgjghghhf

程序可能输出：

hhhhhgggggggffffjjjjj

字符不必排序，只需组合在一起。

是否有一种算法或 class 种算法旨在执行此操作？

Answer 1

您可以计算所有出现次数（复杂度 O(n)），然后通过重复他出现的每 char 次从这些计数中创建 string（复杂度 O(n)，可能甚至更好 - 类似于 (O(n/26)，它取决于 chars 唯一性）。对于长字符串，这可能比简单地 sort.

更好

示例：

const input = "ghfgjggjhfjfjgjghghhf"

const count = [...input].reduce(
  (acc, char) => ({
      ...acc,
      [char]: (acc[char] ? acc[char] + 1 : 1)
  }),
  {}
)

const res = Object.entries(count)
                  .reduce((acc, [char, count]) => acc + char.repeat(count), "")

console.log(res)

Answer 2

在 JavaScript 中，您可以通过以下方式实现：

将源字符串拆分为字符数组
对字符数组进行排序
将字符数组连接成一个字符串

请参阅以下工作片段：

source = "ghfgjggjhfjfjgjghghhf";
sourceArray = source.split("");
outArray = sourceArray.sort();
output = outArray.join("");
console.log(output);

输出：

ffffggggggghhhhhjjjjj

请注意，由于使用了.sort()，字符实际上是按字母顺序排序的。在您的问题中，您声明只要字符分组，它的排序方式并不重要。

这里还有一些使用相同方法的快速 Python：

source = 'ghfgjggjhfjfjgjghghhf'
print(''.join(sorted(source)))

我在评论中看到您正在寻找实现此目标的最有效方法。我怀疑我的建议不有效，因为将答案转换为字符数组并再次返回的费用很高。

Answer 3

如果不需要对输出进行排序，您通常会构建一个频率图来保存每个字符的 count，然后在输出中重复 count 次。

这里有一些 Java 代码来说明：

String s = "ghfgjggjhfjfjgjghghhf";

Map<Character, Integer> m = new HashMap<>();
for(char c : s.toCharArray())
    m.put(c, 1 + m.getOrDefault(c, 0));

StringBuilder b = new StringBuilder();
for(char c : m.keySet())
    for(int i=m.get(c); i>=0; i--)
        b.append(c);
System.out.println(b);

输出：

fffffgggggggghhhhhhjjjjjj

将字符串中的字符组合在一起的算法

Algorithm to group characters together in string

sorting

algorithm

grouping