算法设计题(要求同上):已知长度为n的线性表A采用顺序结构存储,请写一算法,找出该线性表中值第二小元素的位置。
时间: 2024-02-18 16:01:26 浏览: 30
这道题可以使用一趟扫描的方法来解决,以下是我的算法设计:
1. 定义两个变量 min 和 sec_min,分别表示最小值和第二小的值。将 min 和 sec_min 的初始值都设为线性表A第一个元素的值。
2. 遍历线性表A中的每个元素,如果当前元素的值小于 min,则将 min 更新为当前元素的值,同时将 sec_min 更新为原 min 的值;如果当前元素的值大于等于 min 且小于 sec_min,则将 sec_min 更新为当前元素的值。
3. 遍历结束后,如果 sec_min 的值没有被更新,则说明线性表A中没有第二小的元素,返回 -1;否则再遍历一遍线性表A,找到第一个值为 sec_min 的元素的下标即可。
以下是代码实现:
```python
def find_second_min_pos(A):
n = len(A)
if n < 2:
return -1
min_val = sec_min_val = A[0]
for i in range(1, n):
if A[i] < min_val:
sec_min_val = min_val
min_val = A[i]
elif A[i] >= min_val and A[i] < sec_min_val:
sec_min_val = A[i]
if sec_min_val == min_val:
return -1
for i in range(n):
if A[i] == sec_min_val:
return i
return -1
```
以上算法的时间复杂度为 O(n),空间复杂度为 O(1)。