将字符串中的字符组合在一起的算法
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 中,您可以通过以下方式实现:
- 将源字符串拆分为字符数组
- 对字符数组进行排序
- 将字符数组连接成一个字符串
请参阅以下工作片段:
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
我正在寻找一种将字符串中的字符组合在一起的算法。例如:
如果我们有这个字符串:
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 中,您可以通过以下方式实现:
- 将源字符串拆分为字符数组
- 对字符数组进行排序
- 将字符数组连接成一个字符串
请参阅以下工作片段:
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