请设计一个算法，要求将长度为n的数组Arr中，元素循环后移t个位置，例如Arr[0]移动到Arr[t]。要求元素移动或交换的次数为O(n)。采用类C语言描述。

算法思路：

1. 将前n-t个元素逆序；
2. 将后t个元素逆序；
3. 将整个数组逆序。

代码实现：

void reverse(int *arr, int start, int end){
int temp;
while(start < end){
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}

void shift(int *arr, int n, int t){
t = t % n; // t可能大于n，需要取模
reverse(arr, 0, n-t-1);
reverse(arr, n-t, n-1);
reverse(arr, 0, n-1);
}

时间复杂度：O(n)

相关问题

设计算法，数组中查找一个数，找到放在第一位，没找到所有元素后移一个，将其放在首位，使用C语言

在C语言中，你可以使用双指针方法来实现这样的算法。这个过程通常称为“滑动窗口”或“滚动数组”的思想。下面是一个简单的示例函数，它会遍历数组并在找到目标值时将它移动到数组的最前面：

#include <stdio.h>

void findAndShift(int arr[], int n, int target) {
    if (n == 0 || arr[0] == target) return; // 如果数组为空或已找到目标，直接返回

    int left = 0, right = n - 1;
    while (left <= right) {
        if (arr[left] == target) {
            // 找到了目标，交换左边界位置和第一个元素
            int temp = arr[left];
            arr[left] = arr[0];
            arr[0] = temp;

            // 移动右边界，寻找下一个可能的目标
            right--;
        } else if (arr[right] == target) {
            // 直接将右边界目标放到第一个位置，然后向左移动左边界
            arr[0] = arr[right];
            right--;
        } else {
            // 没有找到目标，两边都向中间靠拢
            arr[left] = arr[left + 1]; // 左边元素移到左边
            left++;
        }
    }
}

int main() {
    int arr[] = {5, 3, 7, 1, 9, 2, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 7;
    findAndShift(arr, n, target);
    
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

在这个例子中，`findAndShift` 函数接受一个整数数组、数组长度以及目标值作为输入。如果找到目标值，它会在数组头部替换它；如果没有找到，它会把其他非目标元素逐步移动到左侧。运行 `main` 函数，可以看到输出数组的变化。

#include <stdio.h>int main() { int arr[10] = {10, 20, 30, 40, 50, 60, 70, 80, 90}; // 已排序数组 int n = 9; // 数组长度 int i, j; // 找到35应该插入的位置 for (i = n - 1; i >= 0 && arr[i] > 35; i--) { arr[i + 1] = arr[i]; // 后移元素 } // 将35插入该位置 arr[i + 1] = 35; // 输出结果 for (i = 0; i < n + 1; i++) { printf("%d ", arr[i]); } printf("\n"); return 0;}

这段代码的功能是将一个整数35插入已排序的整数数组中，保持数组元素仍然有序。具体实现方式是从后往前遍历数组，找到35应该插入的位置，然后将35插入该位置。

代码中，数组长度为10，初始已排序数组为{10, 20, 30, 40, 50, 60, 70, 80, 90}。变量i从n-1开始，即从数组最后一个元素开始遍历。如果当前元素大于35，则将该元素后移一位，腾出位置给35。最终将35插入该位置，输出结果为插入后的有序数组。

这是一种简单的插入排序算法，时间复杂度为O(n)，适用于小规模数据的排序。