C语言数组两段区间互换reverse_reg函数实现问题咨询

原有代码的核心问题 #

• 下标计算逻辑完全错误，未考虑起始偏移s，j - i + 1的计算极易出现越界访问
• i > k / 2的判断没有任何通用逻辑支撑，仅适用于当前测试的特殊场景，无法适配任意起始/结束下标输入
• 单次遍历交换的思路没有考虑两个区间长度不一致的情况，会导致未处理的元素被覆盖，最终结果错误

推荐实现思路：三次反转法 #

这是相邻区间互换（即数组旋转问题）的经典O(n)时间、O(1)空间最优解法，步骤如下：

1. 反转第一个闭区间[s, k]
2. 反转第二个闭区间[k+1, j-1]（因j是开区间边界，第二个区间的实际末尾下标为j-1）
3. 反转整个待操作的大区间[s, j-1]

完整可运行代码 #

// 先实现swap函数（如果环境没有内置）
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 辅助函数：反转数组arr的[left, right]闭区间
void reverse(int *arr, int left, int right) {
    while(left < right) {
        swap(&arr[left], &arr[right]);
        left++;
        right--;
    }
}

void reverse_reg(int *arr, int s, int k, int j)
{
    // 输入合法性校验
    if (arr == NULL || s >= k || k >= j - 1) {
        return;
    }
    reverse(arr, s, k);
    reverse(arr, k + 1, j - 1);
    reverse(arr, s, j - 1);
}

示例验证 #

你给出的测试场景下执行逻辑：

• 原数组：[1,2,5,7,8,a,b,c]
• 反转第一个区间[0,4]得到：[8,7,5,2,1,a,b,c]
• 反转第二个区间[5,7]得到：[8,7,5,2,1,c,b,a]
• 反转整个区间[0,7]得到：[a,b,c,1,2,5,7,8]，完全符合预期输出。

内容的提问来源于stack exchange，提问作者loukritios