YingJoy's Blog
0%

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

Posted on Edited on

如下代码

  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