CB3-将字符串中所有'S'提到所有'H'之前
[[#类似快速排序的双指针（不稳定）]]
代码实现
| C |
|---|
| /**
* 将字符串中所有'S'提到所有'H'之前
* 算法思想：遇到'S'直接前移，遇到'H'入栈，最后将栈中'H'依次输出
* @param A 字符串数组
*/
void fun(char A[]) {
// k指向下一个'S'应该放置的位置
int k = 0;
// 初始化栈，用于存储'H'
Stack s;
s.top = -1;
// 第一次遍历：处理所有字符
for (int i = 0; A[i] != '\0'; i++) {
// 如果是'S'，直接放到前面
if (A[i] == 'S') {
A[k++] = A[i]; // 'S'前移
}
// 如果是'H'，入栈暂存
else if (A[i] == 'H') {
// 检查栈是否已满
if (s.top == MAXSIZE - 1) {
printf("栈溢出\n");
return;
}
s.data[++s.top] = A[i]; // 'H'入栈
}
// 其他字符忽略（根据题目要求，假设只有S和H）
}
// 第二次处理：将栈中所有'H'依次放到'S'之后
while (s.top != -1) {
A[k++] = s.data[s.top--]; // 'H'出栈并放置到数组中
}
// 注意：原代码缺少字符串结束符
A[k] = '\0'; // 添加字符串结束符
}
|
算法执行流程图解
执行过程示例：
| Text Only |
|---|
| 原字符串：H S S H H H S \0
0 1 2 3 4 5 6 7
执行过程：
i=0: A[0]='H' → 入栈s，栈：[H]，k=0
i=1: A[1]='S' → A[0]='S'，k=1，栈：[H]
i=2: A[2]='S' → A[1]='S'，k=2，栈：[H]
i=3: A[3]='H' → 入栈s，栈：[H][H]，k=2
i=4: A[4]='H' → 入栈s，栈：[H][H][H]，k=2
i=5: A[5]='H' → 入栈s，栈：[H][H][H][H]，k=2
i=6: A[6]='S' → A[2]='S'，k=3，栈：[H][H][H][H]
栈中元素出栈：
A[3]='H'，k=4，栈：[H][H][H]
A[4]='H'，k=5，栈：[H][H]
A[5]='H'，k=6，栈：[H]
A[6]='H'，k=7，栈：[]
最终结果：S S S H H H H \0
|
算法状态变化图解
| Text Only |
|---|
| 原字符串：H S S H H H S
步骤1：遍历处理
┌─────────────────────────────┐
│ H S S H H H S \0 │
│ ↑ │
│ i=0, A[i]='H' → 入栈 │
│ 栈：[H] │
│ 结果位置：_ _ _ _ _ _ _ │
└─────────────────────────────┘
┌─────────────────────────────┐
│ H S S H H H S \0 │
│ ↑ │
│ i=1, A[i]='S' → 前移 │
│ 栈：[H] │
│ 结果位置：S _ _ _ _ _ _ │
│ ↑ │
│ k=1 │
└─────────────────────────────┘
┌─────────────────────────────┐
│ H S S H H H S \0 │
│ ↑ │
│ i=2, A[i]='S' → 前移 │
│ 栈：[H] │
│ 结果位置：S S _ _ _ _ _ │
│ ↑ │
│ k=2 │
└─────────────────────────────┘
...（继续处理所有H入栈，S前移）
步骤2：栈中元素出栈
栈：[H][H][H][H] → 出栈顺序：H H H H
最终结果：S S S H H H H \0
|
复杂度分析
时间复杂度：O(n)
- 第一次遍历：遍历字符串一次，O(n)
- 栈操作：每次入栈/出栈O(1)
- 第二次处理：出栈所有'H'，最坏O(n)
- 总体时间复杂度：O(n)
空间复杂度：O(n)
- 栈空间：最坏情况下所有'H'都入栈，O(n)
- 辅助变量：k、i等常数个变量，O(1)
- 总体空间复杂度：O(n)
算法优化版本
统计计数
| C |
|---|
| /**
* 优化版本1：统计计数法（空间更优）
*/
void fun_Optimized1(char A[]) {
int s_count = 0; // 统计S的个数
int h_count = 0; // 统计H的个数
// 第一次遍历：统计字符个数
for (int i = 0; A[i] != '\0'; i++) {
if (A[i] == 'S') {
s_count++;
} else if (A[i] == 'H') {
h_count++;
}
}
// 第二次遍历：重新填充数组
int k = 0;
// 先填充所有S
for (int i = 0; i < s_count; i++) {
A[k++] = 'S';
}
// 再填充所有H
for (int i = 0; i < h_count; i++) {
A[k++] = 'H';
}
A[k] = '\0'; // 添加结束符
}
|
双指针
| C |
|---|
| /**
* 优化版本2：双指针法（原地操作）
*/
void fun_Optimized2(char A[]) {
int write_pos = 0; // 写入位置
// 第一次遍历：将所有S前移
for (int i = 0; A[i] != '\0'; i++) {
if (A[i] == 'S') {
A[write_pos++] = 'S';
}
}
// 第二次遍历：将所有H放到S之后
int h_count = 0;
for (int i = 0; A[i] != '\0'; i++) {
if (A[i] == 'H') {
h_count++;
}
}
// 填充H
for (int i = 0; i < h_count; i++) {
A[write_pos++] = 'H';
}
A[write_pos] = '\0';
}
|
类似快速排序的双指针（不稳定）
| C |
|---|
| void moveSToFront(char* str) {
if (str == NULL) return;
int left = 0;
int right = strlen(str) - 1;
while (left < right) {
// 从左边找到第一个'H'
while (left < right && str[left] != 'H') {
left++;
}
// 从右边找到第一个'S'
while (left < right && str[right] != 'S') {
right--;
}
// 如果找到了一对，进行交换
if (left < right) {
char temp = str[left];
str[left] = str[right];
str[right] = temp;
left++;
right--;
}
}
}
|
通用版本（支持多种字符）
| C |
|---|
| /**
* 通用版本：将指定字符提到前面，其他字符放到后面
* @param A 字符串数组
* @param priority_char 优先字符（提到前面）
*/
void fun_General(char A[], char priority_char) {
int k = 0;
Stack s;
s.top = -1;
for (int i = 0; A[i] != '\0'; i++) {
if (A[i] == priority_char) {
A[k++] = A[i];
} else {
if (s.top == MAXSIZE - 1) {
printf("栈溢出\n");
return;
}
s.data[++s.top] = A[i];
}
}
// 将栈中其他字符依次输出
while (s.top != -1) {
A[k++] = s.data[s.top--];
}
A[k] = '\0';
}
|
算法特点
核心思想：
1. 分类处理：将字符分为两类（优先字符和其他字符）
2. 即时处理：优先字符立即前移
3. 延迟处理：其他字符暂存栈中
4. 统一输出：最后将栈中字符统一输出
关键技巧：
- 双缓冲策略：直接前移 vs 栈暂存
- 原地修改：不使用额外数组空间
- 顺序保持：同类字符保持原有相对顺序
与其他方法对比：
| 方法 |
时间复杂度 |
空间复杂度 |
特点 |
| 栈方法 |
O(n) |
O(n) |
保持相对顺序 |
| 计数法 |
O(n) |
O(1) |
不保持相对顺序 |
| 排序法 |
O(n log n) |
O(1) |
不保持相对顺序 |
应用场景：
- 字符串重排
- 数据分类整理
- 优先级处理
这种算法巧妙地利用了栈的特性，实现了高效的字符重排，在实际应用中很有价值。
双指针技术实现（空间复杂度O(1)）
是的，完全可以使用双指针技术实现相同效果，且空间复杂度为O(1)！
| C |
|---|
| /**
* 使用双指针技术将字符串中所有'S'提到所有'H'之前
* 空间复杂度：O(1) - 只使用常数额外空间
* @param A 字符串数组
*/
void fun_TwoPointers(char A[]) {
if (A == NULL || A[0] == '\0') return;
// 统计S和H的个数
int s_count = 0, h_count = 0;
for (int i = 0; A[i] != '\0'; i++) {
if (A[i] == 'S') {
s_count++;
} else if (A[i] == 'H') {
h_count++;
}
}
// 使用双指针重新填充数组
int write_pos = 0; // 写入位置指针
// 先写入所有S
for (int i = 0; i < s_count; i++) {
A[write_pos++] = 'S';
}
// 再写入所有H
for (int i = 0; i < h_count; i++) {
A[write_pos++] = 'H';
}
// 添加字符串结束符
A[write_pos] = '\0';
}
|
更优雅的双指针实现
| C |
|---|
| /**
* 一次遍历的双指针实现
* @param A 字符串数组
*/
void fun_TwoPointers_Elegant(char A[]) {
if (A == NULL || A[0] == '\0') return;
// 第一次遍历：统计各类字符个数
int counts[256] = {0}; // ASCII字符计数数组
for (int i = 0; A[i] != '\0'; i++) {
counts[(unsigned char)A[i]]++;
}
// 第二次遍历：按优先级重新填充
int write_pos = 0;
// 先写入所有S（优先字符）
for (int i = 0; i < counts['S']; i++) {
A[write_pos++] = 'S';
}
// 再写入所有H
for (int i = 0; i < counts['H']; i++) {
A[write_pos++] = 'H';
}
A[write_pos] = '\0';
}
|
保持相对顺序的双指针实现
| C |
|---|
| /**
* 保持字符相对顺序的双指针实现
* @param A 字符串数组
*/
void fun_TwoPointers_PreserveOrder(char A[]) {
if (A == NULL || A[0] == '\0') return;
// 创建临时数组存储结果
int len = 0;
while (A[len] != '\0') len++;
char temp[len + 1]; // 临时数组
// 双指针处理
int write_pos = 0;
// 第一遍：复制所有S
for (int i = 0; A[i] != '\0'; i++) {
if (A[i] == 'S') {
temp[write_pos++] = 'S';
}
}
// 第二遍：复制所有H
for (int i = 0; A[i] != '\0'; i++) {
if (A[i] == 'H') {
temp[write_pos++] = 'H';
}
}
temp[write_pos] = '\0';
// 复制回原数组
for (int i = 0; i <= write_pos; i++) {
A[i] = temp[i];
}
}
|
真正原地的双指针实现
| C |
|---|
| /**
* 真正原地操作的双指针实现（不使用额外数组）
* @param A 字符串数组
*/
void fun_TwoPointers_InPlace(char A[]) {
if (A == NULL || A[0] == '\0') return;
// 统计字符个数
int s_count = 0;
for (int i = 0; A[i] != '\0'; i++) {
if (A[i] == 'S') s_count++;
}
// 计算H的个数
int total_len = 0;
while (A[total_len] != '\0') total_len++;
int h_count = total_len - s_count;
// 直接重写数组
int i = 0;
// 填充S
for (int j = 0; j < s_count; j++) {
A[i++] = 'S';
}
// 填充H
for (int j = 0; j < h_count; j++) {
A[i++] = 'H';
}
A[i] = '\0';
}
|
性能对比测试
| C |
|---|
| // 测试不同方法的性能对比
void performance_test() {
char test1[] = "HSSHHHS";
char test2[] = "SHSHSHSH";
char test3[] = "HHHHHHHHSSSSSSSS";
// 测试栈方法
clock_t start = clock();
for (int i = 0; i < 100000; i++) {
char temp[100];
strcpy(temp, test1);
fun_Original(temp); // 栈方法
}
clock_t stack_time = clock() - start;
// 测试双指针方法
start = clock();
for (int i = 0; i < 100000; i++) {
char temp[100];
strcpy(temp, test1);
fun_TwoPointers(temp); // 双指针方法
}
clock_t two_pointer_time = clock() - start;
printf("栈方法耗时: %ld\n", stack_time);
printf("双指针方法耗时: %ld\n", two_pointer_time);
}
|
算法对比分析
空间复杂度对比：
| Text Only |
|---|
| 方法 空间复杂度 额外空间使用
栈方法 O(n) 最坏n个字符的栈空间
双指针方法 O(1) 只使用常数个变量
计数方法 O(1) 只使用计数变量
|
时间复杂度对比：
| Text Only |
|---|
| 方法 时间复杂度 实际操作数
栈方法 O(n) 2n次操作（遍历+栈操作）
双指针方法 O(n) 2n次操作（统计+填充）
计数方法 O(n) 2n次操作（统计+填充）
|
内存访问模式对比：
| Text Only |
|---|
| 栈方法：
读取A[0]→入栈→读取A[1]→前移→...→出栈→写入
访问模式：分散，涉及栈内存操作
双指针方法：
读取A[0]→计数→读取A[1]→计数→...→连续写入
访问模式：更集中，连续内存操作
|
完整测试示例
| C |
|---|
| #include <stdio.h>
#include <string.h>
#include <time.h>
// 测试函数
void test_all_methods() {
char test_cases[][20] = {
"HSSHHHS",
"SHSHSHS",
"SSSHHH",
"HHHSSS",
"S",
"H",
"",
"SSSSSS",
"HHHHHH"
};
int num_tests = sizeof(test_cases) / sizeof(test_cases[0]);
for (int i = 0; i < num_tests; i++) {
char temp1[20], temp2[20];
strcpy(temp1, test_cases[i]);
strcpy(temp2, test_cases[i]);
printf("原字符串: %s\n", temp1);
fun_Original(temp1);
printf("栈方法结果: %s\n", temp1);
fun_TwoPointers(temp2);
printf("双指针结果: %s\n", temp2);
printf("结果一致: %s\n\n",
strcmp(temp1, temp2) == 0 ? "是" : "否");
}
}
|
结论
双指针技术完全可以实现相同效果，且空间复杂度为O(1)，优势包括：
- 空间效率最优：O(1)空间复杂度
- 时间效率相当：同样是O(n)时间复杂度
- 缓存友好：连续内存访问，局部性好
- 实现简单：逻辑清晰，易于理解
选择建议：
- 内存受限场景：选择双指针方法
- 需要保持相对顺序：两种方法都可以，但实现略有不同
- 通用性要求：双指针方法更容易扩展
双指针技术在这个问题上确实是更好的选择！