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

Algorithm to group characters together in string

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

如果我们有这个字符串:

ghfgjggjhfjfjgjghghhf

程序可能输出:

hhhhhgggggggffffjjjjj

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

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

您可以计算所有出现次数(复杂度 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)

在 JavaScript 中,您可以通过以下方式实现:

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

请参阅以下工作片段:

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

输出:

ffffggggggghhhhhjjjjj

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

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

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

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

如果不需要对输出进行排序,您通常会构建一个频率图来保存每个字符的 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