写出顺序查找算法并分析其时间复杂度。
时间: 2023-06-03 19:03:56 浏览: 82
顺序查找算法是一种简单直观的查找算法,其主要思想是逐个比较待查找元素与查找区间内的元素,直到找到目标元素或查找结束为止。其时间复杂度为O(n),最坏情况下需要遍历整个查找区间。
下面是顺序查找算法的代码实现:
```
int sequentialSearch(int arr[], int n, int target) {
for(int i = 0; i < n; i++) {
if(arr[i] == target) {
return i;
}
}
return -1;
}
```
其中,arr表示待查找数组,n表示数组大小,target表示待查找的目标元素。在遍历数组时,如果找到目标元素,直接返回该元素的下标;如果遍历整个数组还未找到目标元素,返回-1表示查找失败。
相关问题
实现顺序查找算法,写出代码
顺序查找算法是一种简单的查找算法,它的实现过程是从数据的第一个元素开始逐个比较,直到找到匹配的元素或者遍历完所有元素为止。
以下是顺序查找算法的基本代码实现:
```python
def sequential_search(arr, target):
"""
顺序查找算法
:param arr: 待查找的数据
:param target: 目标元素
:return: 目标元素在数据中的位置,如果不存在则返回-1
"""
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
```
使用示例:
```python
arr = [1, 3, 5, 7, 9]
target = 5
result = sequential_search(arr, target)
if result == -1:
print("元素不存在")
else:
print("元素在数组中的位置为:", result)
```
输出结果:
```
元素在数组中的位置为: 2
```
需要注意的是,顺序查找算法的时间复杂度为O(n),在数据量较大时效率较低,可以考虑使用其他查找算法来优化。
用c/c++完整写出代码设计算法以删除顺序表中重复的元素,并分析算法的时间性能
以下是使用C++编写的删除顺序表中重复元素的算法:
```cpp
template<typename T>
void deleteRepeat(vector<T>& v) {
int i = 0, j = 0;
int n = v.size();
unordered_set<T> s;
while (j < n) {
if (s.find(v[j]) == s.end()) {
s.insert(v[j]);
v[i++] = v[j];
}
j++;
}
v.resize(i);
}
```
该算法使用了一个`unordered_set`来保存已经出现过的元素,然后遍历整个数组,如果当前元素没有出现过,则将其加入`unordered_set`中,并将其放到数组的前面。由于使用了`unordered_set`,查找元素的时间复杂度为O(1)。因此,该算法的时间复杂度为O(n)。
以下是完整的测试代码:
```cpp
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
template<typename T>
void deleteRepeat(vector<T>& v) {
int i = 0, j = 0;
int n = v.size();
unordered_set<T> s;
while (j < n) {
if (s.find(v[j]) == s.end()) {
s.insert(v[j]);
v[i++] = v[j];
}
j++;
}
v.resize(i);
}
int main() {
vector<int> v1{ 1,1,2,2,3,3,4,4,5,5 };
vector<char> v2{ 'a', 'b', 'c', 'c', 'd', 'd', 'e', 'e' };
vector<string> v3{ "hello", "world", "hello", "world", "hello" };
deleteRepeat(v1);
deleteRepeat(v2);
deleteRepeat(v3);
cout << "v1: ";
for (auto x : v1) cout << x << " ";
cout << endl;
cout << "v2: ";
for (auto x : v2) cout << x << " ";
cout << endl;
cout << "v3: ";
for (auto x : v3) cout << x << " ";
cout << endl;
return 0;
}
```
输出结果为:
```
v1: 1 2 3 4 5
v2: a b c d e
v3: hello world
```
可以看到,该算法成功地删除了顺序表中的重复元素,并且时间复杂度为O(n)。