对字符串中的所有字符进行排序 [英] Sort all characters in a string

问题描述

我正在尝试解决这个问题，我想对字符串中的字符数组进行排序

I'm trying to solve this problem where I want to sort array of characters in a string

问题：

对字符数组进行排序（仅ASCII，而不是UTF8）。

输入：字符串字符，例如完整的英语句子，以换行符或NULL分隔。可以重复。

Input: A string of characters, like a full English sentence, delimited by a newline or NULL. Duplicates are okay.

例如：这很容易

输出：一个字符串字符，按其ASCII值的排序顺序。您可以覆盖现有阵列。

Output: A string of characters, in sorted order of their ASCII values. You can overwrite the existing array.

例如：Taehiisssy

eg: Taehiisssy

解决方案复杂度：争取线性时间和恒定额外的空间。

Solution Complexity: Aim for linear time and constant additional space.

我知道在JavaScript中您可以做类似

I know that in JavaScript you can do something like

const sorted = str.split('').sort().join('')

编辑：我正在尝试查看是否可以使用 charCodeAt（i）方法

I'm trying to see if I can make use of charCodeAt(i) method if I can get anything out of it.

但这将是O（nLogN）^^非线性（+额外的O（N）用于拆分）

But this would be O(nLogN) ^^ not linear (+extra space O(N) for split)

但是在恒定空间中，我们如何对字符数组进行排序？

But in constant space, how would we sort array of characters?

推荐答案

字符表示累计计数

Character-by-character formulate a cumulative count

const s="This is easy";

// Create an array which will hold the counts of each character, from 0 to 255 (although strictly speaking ASCII is only up to 127)
let count = Array(256).fill(0);

// Look at each character in the input and increment the count for that character in the array.
for(let i=0; i<= s.length; i++) {
  c=s.charCodeAt(i);
  count[c]++;
}

let out="";
// Now scan through the character count array ...
for(let i=0; i<= 255; i++) {
// And for each character, e.g. "T", show it the number of times you saw it in the input
  for(let rep=0; rep<count[i]; rep++){
    out+=String.fromCharCode(i);
  }
}

console.log(out);

表格大小恒定，长度为256个数字（或您希望允许的任何数量的不同符号）。

This only uses a constant table size, 256 numbers long (or whatever number of different symbols you wish to allow).

花费的时间线性依赖于表中字符的数量输入字符串（假设当该字符的计数为零时，几乎不花时间在内部FOR循环上）。

And the time it takes is linearly dependent on the number of characters in the input string (assuming almost no time is spent on the inner FOR loop when the count is zero for that character).

这篇关于对字符串中的所有字符进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！