C语言指定范围[L,U]内数组元素反转的代码问题排查

问题描述 #

需要实现功能：给定包含n个整数的数组，以及下界L和上界U，将数组中处于闭区间[L,U]内的元素进行反转。现有代码在部分场景下输出结果错误，比如以下样例：

样例细节 #

• 样例输入：

  10 -7 5
  -10 -9 5 -2 -3 7 10 6 -8 -5

• 预期输出：

  -10 -9 -5 -3 -2 7 10 6 -8 5

• 实际输出：

  -10 -9 -5 -2 -3 7 10 6 -8 5

现有错误代码 #

#include <stdio.h>
int main() {
  int x, arr[100], n, l, u, a, temp, temp1;
  scanf("%d%d%d", &n, &l, &u);
  for (int i = 0; i < n; i++) {
    scanf("%d", &x); // read elements of an array
    arr[i] = x;
  }
  a = n / 2;
  for (int i = 0; i < a; i++) {
    for (int j = a; j < n; j++) {
      if (arr[i] >= l && arr[i] <= u) {
        if (arr[j] >=l && arr[j] < u) {
          temp = arr[j];
          temp1 = arr[i];
          arr[i] = temp;
          arr[j] = temp1;
        }
      }
    }
  }

  for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
  }
}

错误分析 #

1. 核心逻辑错误：原代码将数组对半拆分后交换元素，完全不符合"反转区间[L,U]内元素"的需求，思路方向错误。
2. 条件判断错误：第二个判断条件arr[j] < u漏掉了等于，应该是arr[j] <= u，导致等于上界U的元素无法被正确处理。
3. 重复交换问题：嵌套循环会导致符合条件的元素被多次交换，打乱预期的反转顺序。

正确实现思路（双指针法） #

使用双指针从数组两端向中间遍历，专门定位区间[L,U]内的元素并交换，直到指针相遇：

• 左指针left从数组头部开始，向右移动，直到找到第一个处于[L,U]内的元素
• 右指针right从数组尾部开始，向左移动，直到找到第一个处于[L,U]内的元素
• 若left < right，交换两个指针指向的元素，然后left++、right--，重复上述步骤
• 当left >= right时，停止操作，此时区间内元素已完成反转

修正后的代码 #

#include <stdio.h>

int main() {
    int arr[100], n, l, u;
    scanf("%d%d%d", &n, &l, &u);
    
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    int left = 0, right = n - 1;
    while (left < right) {
        // 左指针找第一个在[L,U]内的元素
        while (left < right && !(arr[left] >= l && arr[left] <= u)) {
            left++;
        }
        // 右指针找第一个在[L,U]内的元素
        while (left < right && !(arr[right] >= l && arr[right] <= u)) {
            right--;
        }
        // 交换元素
        if (left < right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
    
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

测试上述样例输入，会得到符合预期的输出结果。

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