Leetcode算法入门与数组丨3. 数组基础

前言

Datawhale组队学习丨9月Leetcode算法入门与数组丨打卡笔记

这篇博客是一个 入门型 的文章，主要是自己学习的一个记录。

内容会参考这篇笔记（很详细）：LeetCode 算法笔记（Leetcode-Notes）

1 数组简介

数组定义

数组（Array）：一种线性表数据结构。它使用一组连续的内存空间，来存储一组具有相同类型的数据，是实现线性表的顺序结构存储的基础。

• 线性表：相同类型的数据元素排成线一样的结构，每个元素最多有前、后两个方向。数**组、栈、队列、链表 **都是线性表结构。
• 连续的内存空间：线性表中顺序存储结构，占用的内存空间连续，也就是说相邻数据元素之间，物理内存上的存储位置相邻。

随机访问数据元素

数组可以根据下标，直接随机指定到某一个元素存放的位置进行访问，也就是说数组具有随机访问的特点。

在定义数组的时候，首先计算机会给数组分配一组连续的存储空间，其中第一个元素的地址称为首地址，之后的元素都具有下标索引和内存地址。计算机通过地址来访问数据元素，并通过寻址公式计算出对应元素的内存地址。

寻址公式
$$下标i对应的数据元素地址=数组首地址+i\times 单个数据元素所占内存大小$$
多维数组

上面介绍的数组只有一个维度，是一维数组，其数据元素也是单下标索引。

在实际生活中，经常会遇到二维或者多为的数据，那么这些数据的存储可能就会用到多维数组。例如二维数组，可以看作是一个特殊的一维数组，即一维数组中的元素也是一个数组。

不同编程语言中数组的实现

不同编程语言中数组的实现可能会有所不同，以下是几种常见编程语言中数组的实现方式：

1. C语言：C语言中的数组是一组相同类型的连续内存空间。可以通过声明数组变量并指定大小来创建数组，例如： int arr[5]; 。数组元素可以通过索引访问，索引从0开始，例如： arr[0] = 10; 。

2. Java：Java中的数组也是一组相同类型的连续内存空间。可以通过声明数组变量并使用 new 关键字来创建数组，例如： int[] arr = new int[5]; 。数组元素同样可以通过索引访问，例如： arr[0] = 10; 。

3. Python：Python中的数组可以使用列表（List）来实现。列表可以包含不同类型的元素，并且可以动态调整大小。可以使用方括号创建列表，例如： arr = [1, 2, 3, 4, 5] 。可以通过索引访问和修改列表元素，例如： arr[0] = 10 。

4. JavaScript：JavaScript中的数组也可以使用方括号创建，例如： var arr = [1, 2, 3, 4, 5]; 。与Python类似，JavaScript数组可以包含不同类型的元素，并且可以动态调整大小。可以通过索引访问和修改数组元素，例如： arr[0] = 10; 。

2 数组的基本操作

增、删、改、查 基本上涉及这四种操作。

2.1 访问元素

访问数组中第 $i$ 个元素：

1. 检查 $i$ 的范围是否在合法的区间内，即 $0\le i\le len(nums)-1$ 。超出范围内的访问为非法访问。
2. 如果是合法访问，则由给定下标得到元素值。

# 从数组 nums 中读取下标为 i 的数据元素值
def value(nums, i):
    if 0 <= i <= len(nums) - 1:
        print(nums[i])
        
arr = [0, 5, 2, 3, 7, 1, 6]
value(arr, 3)
1
2
3
4
5
6
7

2.2 查找元素

查找数组中元素值为 $val$ 的位置：

1. 建立一个基于下标的循环，每次将 $val$ 与当前数据元素 $nums[i]$ 进行比较。
2. 在找到元素的时候返回元素下标。
3. 遍历完找不到时可以返回一个特殊值（例如 −1）。

# 从数组 nums 中查找元素值为 val 的数据元素第一次出现的位置
def find(nums, val):
    for i in range(len(nums)):
        if nums[i] == val:
            return i
    return -1

arr = [0, 5, 2, 3, 7, 1, 6]
print(find(arr, 5))
1
2
3
4
5
6
7
8
9

2.3 插入元素

添加元素到列表末尾：

arr = [1, 2, 3, 4, 5]
arr.append(6)
print(arr)  # 输出：[10, 2, 3, 4, 5, 6]
1
2
3

插入元素到指定位置：

arr = [1, 2, 3, 4, 5]
arr.insert(2, 7)  # 在索引为2的位置插入元素7
print(arr)  # 输出：[10, 2, 7, 3, 4, 5, 6]
1
2
3

2.4 改变元素

将元素中第 $i$ 个元素值改为 $val$ ：

1. 检查 $i$ 的范围是否在合法的区间内，即 $0\le i\le len(nums)-1$ 。超出范围内的访问为非法访问。
2. 如果是合法访问，则将第 $i$ 个元素值赋值为 $val$。

def change(nums, i, val):
    if 0 <= i <= len(nums) - 1:
        nums[i] = val
        
arr = [0, 5, 2, 3, 7, 1, 6]
i, val = 2, 4
change(arr, i, val)
print(arr)
1
2
3
4
5
6
7
8

2.5 删除元素

Python中删除数组元素的几种常见方法：

1. 删除数组尾部元素：

arr = [1, 2, 3, 4, 5]
arr.pop()  # 删除并返回最后一个元素
print(arr)  # 输出：[1, 2, 3, 4]
1
2
3

2. 删除数组指定位置上的元素：（首先要检查下标是否合法，合法之后再进行之后操作）

arr = [1, 2, 3, 4, 5]
arr.pop(2)  # 删除索引为2的元素
print(arr)  # 输出：[1, 2, 4, 5]
1
2
3

3. 基于条件删除元素：

arr = [1, 2, 3, 4, 5]
arr.remove(3)  # 删除所有等于3的元素
print(arr)  # 输出：[1, 2, 4, 5]
1
2
3

3 总结

数组作为最基本的顺序结构存储方式，支持随机访问。在执行增删改查操作时，不同的操作对于时间复杂度的影响也不同。

当涉及到数组的增删改查操作时，不同操作的时间复杂度会有所不同。以下是一些示例：

1. 访问元素（随机访问）：

• 时间复杂度：O(1)
• 无论数组多大，通过索引直接访问元素的时间是恒定的，因为数组元素在内存中是连续存储的。例如，访问数组中的第一个元素或最后一个元素都只需要一步操作。

2. 插入元素：

• 在数组的末尾插入元素：

  • 时间复杂度：O(1)
  • 当在数组末尾插入元素时，只需要将元素添加到数组的最后一个位置。

• 在数组的其他位置插入元素：

  • 时间复杂度：O(n)
  • 当在数组的其他位置插入元素时，需要将插入位置后面的所有元素向后移动一位，以腾出空间插入新元素。

3. 删除元素：

• 删除数组末尾的元素：

  • 时间复杂度：O(1)
  • 当删除数组末尾的元素时，只需要将数组的长度减一即可。

• 删除数组的其他位置的元素：

  • 时间复杂度：O(n)
  • 当删除数组的其他位置的元素时，需要将删除位置后面的所有元素向前移动一位，以填补删除的空缺。

4. 修改元素：

• 时间复杂度：O(1)
• 通过索引直接访问并修改数组中的元素，时间复杂度为常数。

task03

0066. 加一

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        digits = [0] + digits
        digits[len(digits)-1] += 1
        for i in range(len(digits)-1, 0, -1):
            if digits[i] != 10:
                break
            else:
                digits[i] = 0
                digits[i-1] += 1

        if digits[0] == 0:
            return digits[1:]
        else:
            return digits
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

0724. 寻找数组的中心下标

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        sum = 0
        for i in range(len(nums)):
            sum += nums[i]
        sum_t = 0
        for i in range(len(nums)):
            if sum_t * 2 + nums[i] == sum:
                return i
            sum_t += nums[i]
        return -1
            
1
2
3
4
5
6
7
8
9
10
11
12

0189. 轮转数组

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k = k % n
        self.reverse(nums, 0, n-1)
        self.reverse(nums, 0, k-1)
        self.reverse(nums, k, n-1)

    def reverse(self, nums: List[int], left: int, right: int) ->None:
        while left < right :
            temp = nums[left]
            nums[left] = nums[right]
            nums[right] = temp
            left += 1
            right -= 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

task04

48. 旋转图像

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        matrix_new = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                matrix_new[j][n-i-1] = matrix[i][j]
        
        matrix[:] = matrix_new
1
2
3
4
5
6
7
8
9
10
11
12

54. 螺旋矩阵

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix: return []
        l, r, t, b, res = 0, len(matrix[0]) - 1, 0, len(matrix) - 1, []
        while True:
            for i in range(l, r+1): res.append(matrix[t][i])
            t += 1
            if t > b : break
            for i in range(t, b+1): res.append(matrix[i][r])
            r -= 1
            if l > r: break
            for i in range(r, l-1, -1): res.append(matrix[b][i])
            b -= 1
            if t > b: break
            for i in range(b, t-1, -1): res.append(matrix[i][l])
            l += 1
            if l > r: break

        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

498. 对角线遍历

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        x, y, m, n, ans = 0, 0, len(mat), len(mat[0]), []
        for j in range(m*n):
            ans.append(mat[x][y])
            if (x + y) % 2 == 0:         # 右上方移动
                if y == n-1:
                    x += 1        # 第一行
                elif x == 0:
                    y += 1        # 最后一列
                else: 
                    x -= 1
                    y += 1                   
            else:
                if x == m-1: 
                    y += 1       # 最后一行
                elif y == 0: 
                    x += 1       # 第一列
                else: 
                    x += 1
                    y -= 1   
        return ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

参考文献

• [1] https://datawhalechina.github.io/leetcode-notes/#/

—— END ——

---

如果以上内容有任何错误或者不准确的地方，欢迎在下面 👇 留言。或者你有更好的想法，欢迎一起交流学习~~~

更多精彩内容请前往 AXYZdong的博客