数组

算法

数组是最基础的数据结构,在内存中连续存储,支持随机访问。适用于需要频繁按索引访问元素的场景。

空间复杂度:O(n)

算法讲解

数组(Array)

介绍

数组是计算机科学中最基础的数据结构之一,由相同类型的元素按顺序存储在连续的内存空间中。每个元素通过其索引值(数组下标)来进行唯一标识和访问。

在大多数编程语言中,数组的索引都是从0开始的,所以一个长度为n的数组,其索引范围是0到n-1。

核心特性

  1. 固定大小:在大多数语言中,数组创建后大小固定不变
  2. 连续内存:元素在内存中顺序存储,无额外开销
  3. 随机访问:O(1)时间复杂度直接访问任意元素
  4. 同质性:同一数组中所有元素类型相同
  5. 索引访问:通过数字索引访问元素

基本操作

1. 访问元素

  • 时间复杂度:O(1)
  • 基本语法:array[index]

2. 更新元素

  • 时间复杂度:O(1)
  • 基本语法:array[index] = value

3. 遍历数组

  • 时间复杂度:O(n)

4. 搜索元素

  • 无序数组:O(n)
  • 有序数组:O(log n)(使用二分查找)

5. 插入/删除元素

  • 在数组末尾:O(1)
  • 在数组指定位置:O(n)(需要移动元素)

基础操作

代码实现

Java 实现

▼
Java
复制代码
// 声明和初始化 int[] numbers = new int[5]; // 创建一个长度为5的int数组,默认值都是0 int[] primes = {2, 3, 5, 7, 11}; // 直接使用初始值创建数组 // 访问元素 int firstPrime = primes[0]; // 得到2 // 更新元素 numbers[0] = 10; // 获取数组长度 int length = numbers.length; // 遍历数组 for (int i = 0; i < primes.length; i++) { System.out.println(primes[i]); } // 使用增强for循环遍历 for (int prime : primes) { System.out.println(prime); }

JavaScript 实现

▼
Javascript
复制代码
// 声明和初始化 let numbers = new Array(5); // 创建一个长度为5的数组,元素都是undefined let numbers2 = Array(5).fill(0); // 创建一个长度为5的数组,元素都是0 let primes = [2, 3, 5, 7, 11]; // 直接使用初始值创建数组 // 访问元素 let firstPrime = primes[0]; // 得到2 // 更新元素 numbers[0] = 10; // 获取数组长度 let length = primes.length; // 遍历数组 for (let i = 0; i < primes.length; i++) { console.log(primes[i]); } // 使用for...of循环遍历(类似Java的增强for循环) for (let prime of primes) { console.log(prime); } // 使用forEach方法遍历 primes.forEach(prime => { console.log(prime); });

Python

▼
Python
复制代码
# 声明和初始化 numbers = [0] * 5 # 创建一个长度为5的列表,元素都是0 primes = [2, 3, 5, 7, 11] # 直接使用初始值创建列表 # 访问元素 first_prime = primes[0] # 得到2 # 更新元素 numbers[0] = 10 # 获取数组长度 length = len(primes) # 遍历数组 for i in range(len(primes)): print(primes[i]) # 直接遍历元素(类似Java的增强for循环) for prime in primes: print(prime) # 使用enumerate同时获取索引和值 for index, prime in enumerate(primes): print(f"primes[{index}] = {prime}")

Go

▼
Go
复制代码
package main import "fmt" func main() { // 声明和初始化 var numbers [5]int // 创建一个长度为5的int数组,默认值都是0 primes := [5]int{2, 3, 5, 7, 11} // 直接使用初始值创建数组 // 自动计算长度 primes2 := [...]int{2, 3, 5, 7, 11} // 访问元素 firstPrime := primes[0] // 得到2 // 更新元素 numbers[0] = 10 // 获取数组长度 length := len(primes) // 遍历数组 for i := 0; i < len(primes); i++ { fmt.Println(primes[i]) } // 使用range遍历(类似Java的增强for循环) for _, prime := range primes { fmt.Println(prime) } // 同时获取索引和值 for i, prime := range primes { fmt.Printf("primes[%d] = %d\n", i, prime) } // 输出变量避免未使用错误 fmt.Println(firstPrime, numbers, length, primes2) }

C

▼
C
复制代码
#include <stdio.h> int main() { // 声明和初始化 int numbers[5] = {0}; // 创建一个长度为5的int数组,所有元素为0 int primes[5] = {2, 3, 5, 7, 11}; // 直接使用初始值创建数组 // 访问元素 int firstPrime = primes[0]; // 得到2 // 更新元素 numbers[0] = 10; // 获取数组长度(C中需要手动计算或记住) int length = sizeof(primes) / sizeof(primes[0]); // 遍历数组 for (int i = 0; i < length; i++) { printf("%d\n", primes[i]); } // C没有内置的增强for循环,只能用传统for循环 // 避免未使用变量的警告 printf("First prime: %d, Modified number: %d, Array length: %d\n", firstPrime, numbers[0], length); return 0; }

C++

▼
C++
复制代码
#include <iostream> #include <array> #include <vector> int main() { // 传统C风格数组 int numbers[5] = {0}; // 创建一个长度为5的int数组,所有元素为0 int primes[5] = {2, 3, 5, 7, 11}; // 直接使用初始值创建数组 // C++ std::array(固定大小) std::array<int, 5> stdNumbers = {0, 0, 0, 0, 0}; std::array<int, 5> stdPrimes = {2, 3, 5, 7, 11}; // C++ std::vector(动态大小) std::vector<int> vecNumbers(5, 0); // 5个元素,都是0 std::vector<int> vecPrimes = {2, 3, 5, 7, 11}; // 访问元素 int firstPrime = primes[0]; // 得到2 int firstStdPrime = stdPrimes[0]; int firstVecPrime = vecPrimes[0]; // 更新元素 numbers[0] = 10; stdNumbers[0] = 10; vecNumbers[0] = 10; // 获取数组长度 int length1 = sizeof(primes) / sizeof(primes[0]); // C风格 size_t length2 = stdPrimes.size(); // std::array size_t length3 = vecPrimes.size(); // std::vector // 遍历数组 // C风格 for (int i = 0; i < length1; i++) { std::cout << primes[i] << std::endl; } // 使用基于范围的for循环(C++11,类似Java的增强for循环) for (int prime : stdPrimes) { std::cout << prime << std::endl; } // 使用迭代器 for (auto it = vecPrimes.begin(); it != vecPrimes.end(); ++it) { std::cout << *it << std::endl; } return 0; }

优缺点

优点

  1. 快速访问:O(1)时间复杂度随机访问任意元素
  2. 空间效率高:元素紧密排列,内存利用率高
  3. CPU缓存友好:连续内存布局有利于缓存命中率
  4. 下标访问直观:使用自然数字索引访问简单直观

缺点

  1. 固定大小:创建后大小不可变(Java的原生数组)
  2. 插入删除低效:非尾部操作需要移动元素,时间复杂度O(n)
  3. 内存浪费:预分配过大容量可能造成内存浪费
  4. 空间要求:要求内存中有足够的连续空间

应用场景

  1. 需要快速随机访问的场景,如图像处理、矩阵运算
  2. 大小已知且固定的数据集合
  3. 需要高性能的数值计算或科学计算
  4. 查询频繁但修改较少的数据结构
  5. 作为底层数据结构,许多高级数据结构内部使用数组实现

扩展:动态数组

由于原生数组大小固定的限制,很多编程语言提供了动态数组的实现,比如Java中的ArrayList。

▼
Java
复制代码
import java.util.ArrayList; // 创建动态数组 ArrayList<Integer> list = new ArrayList<>(); // 添加元素 list.add(10); list.add(20); // 指定位置添加元素 list.add(1, 15); // [10, 15, 20] // 访问元素 int value = list.get(0); // 10 // 修改元素 list.set(1, 25); // [10, 25, 20] // 删除元素 list.remove(2); // [10, 25] // 获取大小 int size = list.size(); // 2

具体扩容机制和原理参考:Java ArrayList 的扩容机制是什么? - 面试鸭 - 程序员求职面试刷题神器

扩展:多维数组

多维数组是数组的扩展形式,可以看作是"数组的数组"。最常见的是二维数组,它可以用来表示表格、矩阵等结构。

二维数组

二维数组可以想象成一个表格,有行和列,每个元素需要两个索引来定位:一个表示行,一个表示列。

Java中创建二维数组

▼
Java
复制代码
// 创建一个3行4列的二维数组 int[][] matrix = new int[3][4]; // 创建并初始化二维数组 int[][] gameBoard = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };

访问二维数组元素

▼
Java
复制代码
// 访问第2行第3列的元素(索引从0开始,所以是[1][2]) int element = gameBoard[1][2]; // 得到值6 // 修改元素 gameBoard[0][1] = 10; // 将第1行第2列的元素改为10

遍历二维数组

▼
Java
复制代码
// 使用嵌套for循环遍历 for (int i = 0; i < gameBoard.length; i++) { // 遍历行 for (int j = 0; j < gameBoard[i].length; j++) { // 遍历列 System.out.print(gameBoard[i][j] + " "); } System.out.println(); // 换行 } // 使用增强for循环 for (int[] row : gameBoard) { for (int value : row) { System.out.print(value + " "); } System.out.println(); }

内存布局

在Java中,二维数组实际上是"数组的数组",即第一维存储的是指向第二维数组的引用。因此,Java中的二维数组可以是不规则的(每行的长度可以不同)。

▼
Java
复制代码
// 创建不规则二维数组 int[][] irregular = new int[3][]; irregular[0] = new int[2]; irregular[1] = new int[4]; irregular[2] = new int[3];

多维数组

Java支持两维以上的多维数组,如三维数组(可以想象成多层二维表格)或更高维度的数组。

▼
Java
复制代码
// 创建三维数组 int[][][] cube = new int[3][4][5]; // 3层,每层4行5列 // 访问三维数组的元素 cube[1][2][3] = 100; // 第2层,第3行,第4列

多维数组的应用

  1. 游戏开发:使用二维数组表示游戏地图、棋盘等。
  2. 图像处理:使用二维数组表示像素矩阵。
  3. 矩阵运算:科学计算和线性代数中的矩阵运算。
  4. 数据分析:处理表格数据和多维数据集。
  5. 3D建模:使用三维数组表示空间中的体素数据。

测验

1)在Java中,声明一个长度为10的整型数组,初始值为0到9,正确的代码是什么?

2)如果有一个大小为n的数组,要在索引为k的位置插入一个新元素,最坏情况下的时间复杂度是多少?

3)二维数组int[][] arr = new int[5][4]中共有多少个元素?

4)如何在不使用额外空间的情况下反转一个数组?

测验答案

1)在Java中,声明一个长度为10的整型数组,初始值为0到9,正确的代码是什么?

▼
Java
复制代码
int[] arr = new int[10]; for (int i = 0; i < 10; i++) { arr[i] = i; }

或者直接初始化:

▼
Java
复制代码
int[] arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

2)最坏情况时间复杂度为O(n)。发生在需要在数组头部(k=0)插入元素时,这需要将所有现有元素向后移动一位。

3)二维数组int[][] arr = new int[5][4]中共有多少个元素?共有20个元素。这是一个5行4列的二维数组,总元素个数 = 5 × 4 = 20。

4)如何在不使用额外空间的情况下反转一个数组?使用双指针:

▼
Java
复制代码
public void reverseArray(int[] arr) { int left = 0; int right = arr.length - 1; while (left < right) { // 交换元素 int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; // 移动指针 left++; right--; } }

相关LeetCode热门题目

数组是比较基础的数据结构,并不难理解,很多地方都有数组的使用和体现,建议学完之后通过以下题目练练手:

  1. 53. 最大子数组和 - 寻找具有最大和的连续子数组
  2. 11. 盛最多水的容器 - 使用双指针处理数组
  3. 283. 移动零 - 保持相对顺序将所有零移到末尾
  4. 88. 合并两个有序数组 - 原地合并两个有序数组

刚开始刷题觉得比较难是正常的,大家一定要坚持住,熟悉这里面的种种套路之后就能从容面对大部分题啦,加油!