第一课 数组与链表

数组的原理和应用

• 数组 「Array」是编程语言内置的一种数据结构，存储有限个有序同类型元素的容器；
• 有静态数组 「Static Array」 和 动态数组「Dynamic Array」 之分，即不可扩容数组和可扩容数组，通常数组指的是静态数组；
• 数组在内存中是一段连续的存储空间；
• 数组的特点是能够随机访问元素。

声明方式：

• Go：var arr = [5]int ；Go 中数组不支持追加元素和删除元素，创建出来后可以修改有效索引位置上的元素值；若要强制进行追加或删除操作会重新创建数组，即，重新分配内存，再把数据拷贝到新数组上。
• Python：arr = []；Python 中数组支持追加元素和删除元素，数组初始化后才可以修改有效索引位置上的元素值。

索引和寻址

只需存储首元素地址，就能算出其他元素的内存地址。

数组的关键是索引和寻址，寻址原理如下：

// 从 0 开始编号的编程语言的通过寻址公式：
arr[k] = base_address + k * type_size
// 从 1 开始编号的编程语言的通过寻址公式：
arr[k] = base_address + (k-1)*type_size

数组根据首地址和下标，直接计算出对应的内存地址，这是数组能够随机访问的原理。
随机访问对于随机读取和随机更新很方便，但添加或者删除就比较麻烦，需要挪移元素。
数组中查找元素需要遍历，复杂度为 O(n)，二查找查时复杂度为 O(logn)。

数组的操作和时间复杂度

注意：这里的插入和删除元素操作是对 Python 说的，对 Go 语言来说数组是不支持插入和删除操作的、若要插入和删除元素都是O(n) 的复杂度，新创建数组再把需要的元素拷贝到其中。

空间复杂度

练习题

1. 设计一个过滤器需要的元素保留，不需要的忽略，并保留元素顺序。

   func removeDuplicates(nums []int) int {
    if len(nums) <= 1 {
        return len(nums)
    }
    n := 0
    for i := 0; i < len(nums); i++ {
        // 过滤条件，满足条件的保留，没满足的忽略
        if  i == 0 || nums[i] != nums[i-1] {
            nums[n] = nums[i]
            n++
        }
    }
    return n
   }
   

2. 设计一个过滤器需要的元素保留，不需要的忽略，并保留元素顺序。

   func moveZeroes(nums []int)  {
   if len(nums) <= 1 {
       return
   }
   n := 0
   for i := range nums {
       if nums[i] != 0 {
           nums[n] = nums[i]
           n++
       }
   }
   for n < len(nums) {
       nums[n] = 0
       n++
   }
   }
   

3. 设计一个过滤器把需要的元素保存到数组中 ```go func merge1(nums1 []int, m int, nums2 []int, n int) { nums3 := make([]int, 0, n) for i,j := 0, 0; i < m || j < n; {

    // j 越界 j >= n 或者 i，j 还未越界 i < m && j < n
    // 且 nums1[i] <= nums2[j] 时
    // 从 nums[1]中的保存
    if j >= n || (i < m && nums1[i] <= nums2[j]) {
        nums3 = append(nums3, nums1[i])
        i++
    } else {
        nums3 = append(nums3, nums2[j])
        j++
    }
   

   } copy(nums1, nums3) }

func merge(nums1 []int, m int, nums2 []int, n int) { cnt := 0 i,j := m - 1, n - 1 // 反序遍历，先把 nums2 放到 nums1 后面的 // nums2 不变，nums1 元素调位 for k := m + n - 1;k >= 0; k— { if j < 0 || (i >= 0 && nums1[i] >= nums2[j]) { nums1[k] = nums1[i] i— } else { nums1[k] = nums2[j] j— } } } ```

设计变长数组

计算机的数据结构中提及的 Array 通常是指 Static Array，Static Array 长度固定不支持扩容，因此很多编程语言在 Static Array 上面封装了一层支持扩容(变长)的数组，Go 语言中的 slice 就是 Static Array，也叫动态数组常见的英文名称是 growable array ,resizable array , dynamic array，mutable array ，vector，c，slice 或者 array list 。

声明方式

• Go：var arr []int，arr := make([]int, 0, length)，arr := make([]int, length)，Go 中 slice 支持追加元素和删除元素，前两种声明方式未初始化前不能通过索引访问，容量够用时无需重新分配内存，不够时进行扩容，即需要重新分配内存，再把原数据拷贝到新的slice 中。
• Python：arr = []，支持追加元素和删除元素，未初始化前不能通过索引访问。

设计要点

• 支持索引与随机访问，即，有 set(i int, val int) 和 get(i int) int 方法。
• 分配多长的连续内存空间，即，有 new(capacity int) 方法。
• 内存空间不够时要扩容
• 未使用内存空间太多时要缩容

实现方式

• 初始化空数组，分配常数空间，记录实际长度（size）和容量（capacity）
• 若内存空间不够，重新申请 2 倍大小的连续空间，把数据拷贝到新内存空间，释放就内存空间

• 若内存空间利用率 size / capacity 不到 25% 时释放一半的内存空间

  复杂度分析

• 均摊 O(1)

• 在空数组中连续插入 n 个元素，总插入或者拷贝次数为 n + n/2 + n/4 + ... < 2n
• 一次扩容到下一次释放，至少需要再删除 n - 2n * 1/4 = 0.5n次

  思考题

  若释放空间的阈值设定为 50%，会发生什么情况？
  会导致频繁扩容，浪费时间。

  链表的原理和应用