跳到主要内容

数组 (Array)

概念与原理​

概念​

数组（Array）是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。 常见的线性表和非线性表有：

  • 线性表：数组、链表、队列、栈
  • 非线性表：树、堆、图

特性​

适合查询多修改少的操作，在使用时需要警惕数据访问越界的问题。。

  • 查询效率快，因为数组的结构特点是，根据偏移量（下标）访问速度快，所以随机访问性好。
  • 插入、删除效率低，由于其是连续的线性结构，在删除和插入时通常都会伴随着数据的搬迁。

性能​

在考虑性能时，通常需要去分析不同API的复杂度；另外，数组和链表通常起到了互补的作用，来应对不同的数据处理场景。数组适合查询，链表适合插入和删除。以下列出了常规情况下不同的API的时间复杂度，但具体问题还需要具体分析。

  • 查询(Access)：
    • 根据下标随机访问的时间复杂度：O(1)
  • 插入(Insert)：
    • 最好情况（末尾插入）时间复杂度：O(1)
    • 最坏情况（头部插入）时间复杂度：O(n)
    • 平均情况时间复杂度：(1+2+...n)/n = O(n)
  • 删除(Delete)：
    • 最好情况（末尾删除）时间复杂度：O(1)
    • 最坏情况（开头删除）时间复杂度：O(n)
    • 平均情况时间复杂度：O(n)

实践应用​

实践一：插入操作优化​

在数组的k个位置插入一个数据，若不涉及排序操作，只被用来存储数据的集合，比较优选的方案是，将第k个位置的数据移动到数据的末尾，再将需要的数据插入到第k位，这样就避免了其他数据的移动，从而提高了插入效率，且时间复杂度被降到O(1). 快排的实现思路就是如此。

实践二：删除操作优化​

通常情况下，删除第k个位置的数据，为了内存的连续性，k后面的数据都需要向前搬迁。 但在不考虑数据的连续性的场景中，则可以将多次删除操作集中在一起操作，从而提升删除效率。具体的做法就是：将需要删除的元素进行标记，并不执行真正的删除操作，当数据没有了更多存储空间时，再触发一次真正的删除操作，这样就能减少因为数据搬迁的次数。 JVM的标记清除垃圾回收算法就是此思想。

实践三：为什么很多编程语言中数组都是从0开始编号？​

  1. 从数组存储的内存模型的角度看，“下标”最确切的定义是“偏移（offset)”，由下面公式分析可得，从0开始编号，避免了 一次CPU执行减法指令
  2. 历史原因（因为C语言的这种设计，之后的有些语言设计都效仿了这种设计，也从一定程度上减少C语音程序员学习其他语言的学习成本，因此沿用了这种设计）
a[k]_addr = base_addr + k * type_size  # 从0开始编号

a[k]_addr = base_addr + (k-1)*type_size  # 从1开始编号

实践四：高级编程语言中封装的容器能否替代数组？​

如：python中的List， java中的ArrayList、C++中vector等； 通常需要根据实际情况来考虑，通常的关注点是性能方面的，比如说：

  • 若不是特别关注性能，使用编程语言中封装的对象即可，因为这些容器封装了常用操作，牺牲了性能，但让使用变得简单，可用于日常的业务开发
  • 若特别关注性能，建议使用原生数组，因为原生性能好，但使用起来相对比较繁琐，一般用于底层框架的开发，如网络库的开发

相关算法题​

数组题目的解法技巧->双指针技巧​

在数组中没有真正意义上的指针，通常把索引当做数组中的指针，

  • 左右指针：两个指针相向而行或者相背而行；
  • 快慢指针：两个指针同向而行，一快一慢；

技巧一、快慢指针​

应用场景：

  • 应用在【原地修改数组】类型的算法题目上
  • 应用在【滑动窗口】类型的算法题目上

实践思路；

  • 让慢指针走在后面，快指针走在前面探路，在根据题目中的要求，写出相关判断条件。
  • 对于滑动窗口的类型而言：慢指针在后，快指针在前，两个指针中间的部分就是【窗口】，算法通过扩大或缩小窗口来解决相关问题。
# 框架Demo
def demo(nums: List[int], val: int) -> int:
    fast, slow = 0, 0
    while fast < len(nums):
        if nums[fast] != val:
            nums[slow] = nums[fast]
            slow += 1
        fast += 1
    return slow

技巧二、左右指针​

常用算法: 二分查找

# 框架Demo
def binary_search(nums: List[int], target: int) -> int:
    # 一左一右两个指针相向而行
    left = 0
    right = len(nums)-1
    while left <= right:
        mid = (right + left) // 2
        if nums[mid] == target:
            return mid 
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1
0%