Python Array List 列表 数据结构

Question

使用 Python 的 List（列表）实现：

class Array:
  def __init__(self, x):
    self.data = list(x)

array1 = Array([1,2,3])

size() —— 数组元素的个数

def size(self):
  return len(self.data)

is_empty() —— 判断数组是否为空

def is_empty(self):
  return True if not self.data else False
  # other ways: 1. self.data == [] ; 2. len(self.data) == 0

at(index) —— 返回对应索引的元素，若越界则报错

def at(self,index):
  if index >= len(self.data):
    raise IndexError("Array index out of range.")
  return self.data[index]

push(item) —— 在数组末尾插入元素

def push(self,item):
  self.data.append(item)

insert(index, item) —— 在指定索引中插入元素，并把后面的元素依次后移

def insert(self, index, item):
  self.data.insert(index, item)

pop() —— 删除在数组末端的元素，并返回其值

def pop(self):
  return self.data.pop()

delete(index) —— 删除指定索引的元素，并把后面的元素依次前移

def delete(self,index):
  self.data.pop(index)

remove(item) —— 删除指定值的元素，并返回其索引（即使有多个元素）

def remove(self,item):
  indexList=[]
  count=0
  for i in range(len(self.data)):
    if self.data[i-count]==item:
      indexList.append(i)
      self.data.pop(i-count)
      count+=1
  return indexList

find(item) —— 寻找指定值的元素并返回其中第一个出现的元素其索引，若未找到则返回 -1

def find(self, item):
  if item in self.data:
    return self.data.index(item)
  else:
    return -1

reverse() —— 翻转数组

def reverse(self):
  temp = []
  size = len(self.data)
  for i in range(size):
    temp.append(self.data[size-1-i])
  self.data = temp

sort() —— 数组排序（升序） O(nlogn)

def sort(self):
  return self.data.sort()  # self.data.sort(reverse = True) 为降序

时间复杂度：

• 在数组的末尾插入/删除、更新、获取某个位置的元素，都是 O(1) 的时间复杂度
• 在数组的任何其它地方插入/删除元素，都是 O(n) 的时间复杂度
• 空间复杂度：O(n)