Java常用数据结构与方法

Java 常用类与算法函数介绍

本文档聚焦”函数的解释说明”：每个方法都给出 作用 / 签名 / 返回值 / 时间复杂度 / 易错点 / 示例。

---

一、Arrays（数组工具类，全部是静态方法）

方法	作用	复杂度	易错点
Arrays.sort(a)	对数组原地排序（基本类型用快排变体；对象用 TimSort）	O(n log n)	基本类型排序不稳定；a 会被直接修改
Arrays.sort(a, (x,y)->x-y)	自定义比较器排序（升序）	O(n log n)	x-y 在差值超 int 范围时可能溢出，超大数用 Integer.compare(x,y)
Arrays.binarySearch(a, key)	在已排序数组中二分查找	O(log n)	数组必须先排序，否则结果未定义；找不到返回负数插入点
Arrays.fill(a, val)	用 val 填充整个数组	O(n)	二维数组 fill 只会复制同一引用，行会共享（坑！）
Arrays.copyOf(a, newLen)	拷贝数组，可截断/扩容	O(n)	新长度 > 原长时多余位置填 0/null
Arrays.copyOfRange(a, from, to)	拷贝 [from, to) 区间	O(to-from)	右边界是开区间
Arrays.equals(a, b)	比较两数组内容是否相等	O(n)	别用 a == b（比的是引用）
Arrays.toString(a)	数组转可读字符串（调试用）	O(n)	多维数组要用 Arrays.deepToString
Arrays.asList(arr)	数组转 List（固定大小）	O(1) 视图	返回的 List 不能 add/remove，否则抛 UnsupportedOperationException

---

二、String（不可变字符串）

关键认知：String 对象不可变，任何”修改”都返回新对象，原串不变。

方法	作用	复杂度	易错点
s.length()	返回字符数（是方法不是字段）	O(1)	别写成 s.length（那是数组的字段）
s.charAt(i)	取第 i 个字符	O(1)	i 越界抛 StringIndexOutOfBoundsException
s.substring(l, r)	截取 [l, r) 子串	O(r-l)	右边界开区间；r 最大为 length()
s.indexOf("x") / lastIndexOf	首次/末次出现位置	O(n)	找不到返回 -1（常用 != -1 判断存在）
s.toCharArray()	转 char[] 便于按索引修改	O(n)	改完用 new String(char[]) 转回
s.split(" ")	按正则分割	O(n)	按 . 等正则元字符要转义 split("\\.")；末尾空串会被丢弃
s.replace(a, b) / replaceAll	替换（前者按字面，后者按正则）	O(n)	replace 不是正则；想用正则才用 replaceAll
s.trim()	去首尾空白	O(n)	中间空格不动；不修改原串
s.contains("x")	是否包含子串	O(n)	—
s.equals(t) / equalsIgnoreCase	内容比较	O(n)	永远用 equals，绝不用 ==
s.compareTo(t)	字典序比较（<0 小于）	O(n)	用于排序
s.startsWith/endsWith	前缀/后缀判断	O(n)	—
s.isEmpty()	长度是否为 0	O(1)	null 调用会 NPE

---

三、StringBuilder（可变字符串，拼接首选）

方法	作用	易错点
append(x)	尾部追加（任意类型）	链式调用 sb.append(a).append(b)
insert(i, x)	在 i 处插入	会改变后续索引
delete(l, r) / deleteCharAt(i)	删除区间/单字符	区间左闭右开
replace(l, r, s)	替换区间内容	—
reverse()	反转	原地修改，返回自身
setCharAt(i, c)	改指定位置字符	—
setLength(0)	清空复用（避免反复 new）	—
toString()	转成 String	最终输出用
length() / capacity()	当前长度 / 内部容量	容量自动扩容，无需关心

---

四、List（以 ArrayList 为主）

方法	作用	复杂度	易错点
add(e)	尾部追加	O(1) 均摊	超容量时扩容为 1.5 倍
add(i, e)	在 i 处插入	O(n)	后续元素后移
get(i) / set(i, e)	取 / 改第 i 个	O(1)	越界抛异常
remove(i) / remove(o)	按下标 / 按对象删除	O(n)	注意重载：remove(1) 删下标1，remove(Integer.valueOf(1)) 删值为1的元素
contains(o) / indexOf(o)	是否包含 / 首次下标	O(n)	对象比较用 equals
size() / isEmpty()	大小 / 空判断	O(1)	—
clear()	清空	O(n)	—
toArray()	转 Object[]	O(n)	转 Integer[] 用 list.toArray(new Integer[0])
sort(cmp)	原地排序	O(n log n)	list.sort((a,b)->a-b)
subList(l, r)	返回原表的视图	O(1)	改子列表会影响原表；不能套 Arrays.sort

---

五、Set（HashSet 哈希集 / TreeSet 有序集）

方法	作用	复杂度	易错点
add(e)	加入（已存在则忽略）	O(1) 均摊	去重核心
contains(e)	是否包含	O(1)	比 List 的 contains 快得多
remove(e)	删除	O(1)	—
size() / isEmpty()	大小 / 空	O(1)	—
TreeSet 专有：first()/last()	最小 / 最大元素	O(log n)	空集调用抛 NoSuchElementException
TreeSet 专有：ceiling(k)/floor(k)	>=k 的最小 / <=k 的最大	O(log n)	找不到返回 null
TreeSet 专有：higher(k)/lower(k)	>k 的最小 / <k 的最大	O(log n)	—

---

六、Map（HashMap 为主）

方法	作用	复杂度	易错点
put(k, v)	存入键值对（覆盖旧值）	O(1)	返回旧值（没有则返回 null）
get(k)	取值	O(1)	未命中返回 null，直接拆箱可能 NPE
getOrDefault(k, d)	取不到返回默认值 d	O(1)	计数场景首选，避免 NPE
containsKey(k)	是否含键	O(1)	别用 map.get(k) != null 判断（值本身可能就是 null）
remove(k)	删键	O(1)	返回被删的值
putIfAbsent(k, v)	键不存在才放	O(1)	常用于首次初始化
computeIfAbsent(k, f)	键不存在时用 f(k) 计算并存入	O(1)	建邻接表/分组极方便：map.computeIfAbsent(k, x->new ArrayList<>()).add(v)
merge(k, v, fn)	合并（键存在用 fn 处理）	O(1)	计数：map.merge(k, 1, Integer::sum)
keySet()/values()/entrySet()	键/值/键值对集合	O(1) 视图	遍历用 entrySet() 最高效
forEach((k,v)->{})	遍历	O(n)	—
size() / isEmpty() / clear()	大小 / 空 / 清空	O(1)	—

---

七、Deque（ArrayDeque，栈和队列都用它）

推荐统一用 ArrayDeque 替代旧类 Stack 和 LinkedList 做栈/队列，性能更好。

当栈用（LIFO）：

方法	作用	等价旧 Stack
push(e)	入栈	addFirst
pop()	出栈（删并返回）	removeFirst
peek()	看栈顶不删	peekFirst

当队列用（FIFO）：

方法	作用	易错点
offer(e)	入队	比 add 安全（满时返回 false 而非抛异常）
poll()	出队（删并返回）	空队列返回 null（别对 null 拆箱）
peek()	看队首不删	空队列返回 null
isEmpty()	判空	用 isEmpty 判断，别用 poll()!=null 当循环条件（会丢元素）

---

八、PriorityQueue（堆）

方法	作用	易错点
offer(e) / add(e)	入堆	O(log n)
poll()	弹出堆顶（最小/最大）	O(log n)；空队列返回 null
peek()	看堆顶不删	O(1)；空返回 null
size() / isEmpty()	大小 / 空	—
构造 new PriorityQueue<>()	默认小根堆（队首最小）	要大根堆必须传比较器 (a,b)->b-a
构造 new PriorityQueue<>(k, cmp)	指定初始容量与比较器	—

---

九、Math（静态数学方法）

方法	作用	注意
Math.abs(x)	绝对值	Integer.MIN_VALUE 取绝对值仍溢出（仍是负值），注意边界
Math.max(a,b) / Math.min(a,b)	最大/最小	重载支持 int/long/float/double
Math.sqrt(x)	平方根（返回 double）	取整 (int)Math.sqrt(x)
Math.pow(a, b)	a 的 b 次幂（double）	整数幂慎用，可能有精度误差
Math.floor/ceil/round	向下/向上取整 / 四舍五入	round 返回 long
Math.random()	[0,1) 随机 double	左闭右开
Math.signum(x)	符号：-1/0/1	—

---

十、Collections（集合工具类，静态方法）

方法	作用	易错点
Collections.sort(list) / sort(list, cmp)	排序（与 list.sort 类似）	对 List 用，不是数组
Collections.reverse(list)	反转	原地修改
Collections.shuffle(list)	随机打乱	抽样/随机化用
Collections.max/min(list)	最大/最小元素	—
Collections.binarySearch(list, key)	二分查找（需先排序）	返回下标
Collections.frequency(c, o)	出现次数	O(n)
Collections.unmodifiableList(list)	返回不可修改视图	防误改，原表改了视图也变
Collections.singletonList(e)	单元素不可变 List	—

---

十一、比较器：Comparator 与 Comparable

两种排序约定方式：

1. Comparable：类自身实现 compareTo（自然序），如 Integer、String 已实现。

2. Comparator：外部比较器，不修改原类，临时指定规则。

易错点：比较器返回值只需保证”负/零/正”的符号正确，未必是 -1/0/1；但当差值可能超出 int 范围（如两个大 long 相减），用 Integer.compare(a,b) / Long.compare(a,b) 避免溢出。

---

十二、算法”函数”使用说明（非类方法，而是套路逻辑）

套路	核心操作	说明
二分查找	mid = l + (r-l)/2；根据 a[mid] 与 target 比调整 l/r	防溢出必须写 l + (r-l)/2 而非 (l+r)/2
快排 partition	选 pivot = a[r]，遍历把 <pivot 的换到左侧，最后把 pivot 归位	返回 pivot 最终下标，用于分治
回溯	做选择 → 递归 → 撤销选择	全局状态（path/used）递归后必须还原，否则污染后续分支
BFS	队列 + 入队标记 visited + 每层取 size	用 !q.isEmpty() 判循环；层序遍历先取 size
滑动窗口	右指针扩张 + while 收缩左指针	收缩条件根据题意写；用 right-left+1 算窗口大小
前缀和	pre[i+1] = pre[i] + a[i]，区间和 pre[r+1]-pre[l]	下标偏移 1，避免边界判断
单调栈	维护”递增/递减”栈，破序时弹栈处理	栈内存的是下标（方便算距离），不是值
并查集	find 带路径压缩，union 按秩合并	find 返回值相等即连通；union 返回 false 说明已有环
动态规划	定义 dp[i] 含义 + 状态转移 + 初始化 + 遍历顺序	0/1 背包容量必须逆序遍历，完全背包才正序

---

十三、速记口诀

• 数组用 Arrays.sort/fill/copyOf/binarySearch（注意先排序再二分）。

• 字符串不可变，改就用 StringBuilder；判等用 equals。

• List 增删慢查慢，Set/Map 查快，去重计数首选 HashSet/HashMap。

• 栈队列统一 ArrayDeque；堆默认小根堆。

• 比较用 Comparator，差值大用 Integer.compare 防溢出。

• 二分中点永远 l + (r-l)/2。