Day 21 impact Blue Bridge Cup - Python data structure and algorithm 03 array

3.1 Definition ：

In contiguous memory space , Store a set of elements of the same type .
A two-dimensional array is actually a linear array that stores the first addresses of other arrays .

3.2 distinguish ：

3.2.1 Elements VS Indexes

[1,2,3]
0,1,2

3.2.2 Array access VS Array search

Array access a[1]=2
Array search Find this element

3.2.3 There are four common operations

There are four common operation time complexity of arrays
visit O(1) The address location can be obtained by calculation , So as to visit
Search for O(N) You need to traverse the array
Insert O(N) You need to move the following elements back
If there's not enough memory , Need to open up a new space , Move the array in
Delete O(N) You need to move the following elements forward

3.3 characteristic

Suitable for reading
It is not suitable for frequent addition and deletion .
scene ： Read more and write less

3.4 python Array common operations

3.4.1 Create array

a=[] # Note that the brackets must be of the same type Otherwise, list 

3.4.2 Additive elements

a.append() # The time complexity is O(1) perhaps O(n),O(1) Add 、O(n) It refers to finding another location to store 
a.insert(2,99); # O(n)

3.4.3 Access elements

Use index （ Subscript ） Access elements

# O(1)
temp=a[2]

3.4.4 Update elements

Use index （ Subscript ） Access elements

# O(1)
a[2]=88

3.4.5 Remove elements

a.remove(88) # O(n) find 88 This element 
a.pop(1) # O(n) Delete the index as 1 You need to move the whole forward by one unit 
a.pop() # O(1) Delete the end No need to move 

3.4.6 Get array length

a=[1,2,3]
size=len(a)
print(size)

3.4.7 Traversal array

# O(n)
for i in a:
print(i)
for index,element in enumerate(a):
print("index at",index,"is:",element)
for i in range(0,len(a)):
print("i:",i,"element",a[i])

3.4.8 Find an element

index=a.index(2) # O(n) Traverse from beginning to end 
print(index)

3.4.9 Array sorting

# O(nLog n)
a=[3,1,2]
a.sort() # From small to large 
print(a)
a.sort(reverse=True) # From big to small 
print(a)