简单算法设计与分析【实验要求】设计一个时间复杂度为O(n)的算法,实现将数组arr[n]中所有元素循环左移k个位置。
时间: 2024-09-08 09:04:03 浏览: 50
为了设计一个时间复杂度为O(n)的算法来实现数组arr[n]中所有元素的循环左移,我们可以采用两个指针的方式,其中一个指针向前移动k个位置,另一个指针负责交换数据。以下是Python语言的一个示例:
```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 实现示例:
```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`)来记录已经遇到过的元素。以下是简单的实现步骤:
```cpp
#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),只要保证哈希集合不会过大。
阅读全文