高效的数组插入和删除元素思想

如下代码

  1. 插入

先将目标位置的元素放到数组最后,再将新元素插入,这样复杂度为O(1)

  1. 删除

定长数组,先标记要删除的元素,等空间不足时在执行清空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class MyArray:
def __init__(self):
self.arr = []

def append(self, num):
self.arr.append(num)

def insert(self, index, num):
"""替换索引位置数据,并将该位置的数据移动到尾部,复杂度为O(1)"""
tmp = self.arr[index]
self.arr[index] = num
self.append(tmp)

def __repr__(self):
return str(self.arr)


class ImmutableLenArray:
"""定长数组,逻辑删除,空间不够再执行删除"""

def __init__(self):
self.max_len = 3
self.arr = []

def append(self, num):
if len(self.arr) == self.max_len:
new_arr = list(filter(lambda x: not x['s'], self.arr))
if len(new_arr) == self.max_len:
print('空间不足')
return
else:
# 清理空间
self.arr = new_arr
self.arr.append({'n': num, 's': 0})

def delete(self, index):
self.arr[index]['s'] = 1

def __repr__(self):
return str([item['n'] for item in self.arr])
  1. 数组越界问题(C++)
1
2
3
4
5
6
7
8
9
int main(int argc, char* argv[]){
int i = 0;
int arr[3] = {0};
for(; i<=3; i++){
arr[i] = 0;
printf("hello world\n");
}
return 0;
}

这里会造成无限循环(视编译器情况)

为什么会无限循环:

1
函数变量存在栈中,设想栈内存空间为Excel的一列,在Excel中从上往下拉4个格子,变量i会先被分配到第4个格子的内存,然后变量arr往上数分配3个格子的内存,但arr的数据是从分配3个格子的第一个格子从上往下存储数据的,当访问第3索引时,这时刚好访问到第4个格子变量i的内存。

20191203151531.png