简单算法设计与分析【实验要求】设计一个时间复杂度为O(n)的算法，实现将数组arr[n]中所有元素循环左移k个位置。

为了设计一个时间复杂度为O(n)的算法来实现数组arr[n]中所有元素的循环左移，我们可以采用两个指针的方式，其中一个指针向前移动k个位置，另一个指针负责交换数据。以下是Python语言的一个示例：

def circular_left_shift(arr, k):
    n = len(arr)
    # 如果k大于n，则相当于对整个数组做一次右移
    k %= n

    # 使用两个指针，一个指向起始位置，一个指向k步后的位置
    start = 0
    end = k
    
    while end < n:
        # 交换两个指针所指向的元素
        arr[start], arr[end] = arr[end], arr[start]
        
        # 指针向后移动
        start += 1
        end += 1
        
    return arr

# 示例
arr = [1, 2, 3, 4, 5]
k = 3
shifted_arr = circular_left_shift(arr, k)
print("Shifted array:", shifted_arr)

相关问题

JAVA简单算法设计与分析【实验要求】设计一个时间复杂度为O(n)的算法，实现将数组arr[n]中所有元素循环左移k个位置。

在 Java 中，设计一个时间复杂度为 O(n) 的算法来实现数组的循环左移操作，可以使用一个辅助数组来保存原数组的内容，然后直接填充到原数组的位置上。这里提供一个简单的步骤：

1. 首先，创建一个新的数组 temp，大小与原数组 arr 相同。

2. 从索引 k 开始遍历原数组 arr，将每个元素复制到临时数组 temp 的对应位置，即 temp[(i - k + n) % n] = arr[i]。这里的 `(i - k + n) % n` 确保了当 k 超过数组长度时，也能正确处理元素的移动。

3. 将临时数组 temp 的内容回填到原数组 arr，即 arr[i] = temp[i]，同样使用 `% n` 来处理溢出的情况。

下面是一个简单的 Java 实现示例：

public void circularLeftShift(int[] arr, int k) {
    if (arr == null || arr.length <= 0) {
        return;
    }
    
    // 辅助数组
    int[] temp = new int[arr.length];
    
    for (int i = 0; i < arr.length; i++) {
        temp[(i - k + arr.length) % arr.length] = arr[i];
    }

    // 回填原数组
    for (int i = 0; i < arr.length; i++) {
        arr[i] = temp[i];
    }
}

用C++实现：遍历数组删除其中的重复元素，要求时间复杂度为O（n），空间复杂度为O（1）

在C++中，为了遍历数组并删除重复元素，同时保持时间和空间复杂度的要求，我们可以使用一个哈希集合（如`std::unordered_set`）来记录已经遇到过的元素。以下是简单的实现步骤：

#include <iostream>
#include <unordered_set>

void removeDuplicates(int arr[], int n) {
    std::unordered_set<int> uniqueSet;
    for (int i = 0; i < n; ++i) {
        if (uniqueSet.find(arr[i]) == uniqueSet.end()) { // 检查元素是否已存在哈希表中
            std::cout << arr[i] << " "; // 如果不存在，打印元素
            uniqueSet.insert(arr[i]); // 将元素添加到哈希集合中
        }
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 4, 5, 6, 7, 7, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    removeDuplicates(arr, n);
    
    return 0;
}

在这个例子中，我们遍历整个数组一次，对于每个元素，如果它不在哈希集合中，我们就打印它并将它加入集合。由于哈希集合查找的时间复杂度接近常数（O(1)），所以整体算法的时间复杂度是线性的（O(n)）。而哈希集合本身的空间复杂度取决于元素的数量，并不是所有元素都存储了两次，因此空间复杂度保持在O(1)，只要保证哈希集合不会过大。