数据结构期末复习：数组核心操作全解析（含代码实现与复杂度分析）

数据结构期末复习：数组核心操作全解析（含代码实现与复杂度分析）

前言
在数据结构期末考试中，数组作为最基础、最常考的数据结构之一，其核心操作是高频考点。本文系统梳理了五大经典数组操作题型——合并、交并集、拆分、去重等，结合实验场景，提供完整 Java 代码实现、时间/空间复杂度分析及易错点提醒，助你高效备考，稳拿高分！

一、复习核心考点清单

1. 两个有序数组合并（双指针经典应用）
2. 无序集合的交集与并集（HashSet 去重特性）
3. 有序集合的交集与并集（利用有序性优化）
4. 字符数组拆分（数字/字母分类）
5. 有序数组去重（两种时间复杂度算法对比）

二、各考点详细解析（含代码 + 思路）

考点1：两个有序数组合并

📌 题目要求

将两个非递减有序数组合并为一个新的非递减有序数组，要求时间复杂度最优。

💡 实现思路

• 核心算法：双指针法（避免冗余排序）
• 时间复杂度：O(n + m)
• 步骤：
  1. 处理边界情况（任一数组为空直接返回另一个）
  2. 初始化双指针i,j和结果指针k
  3. 比较元素，小者入结果数组，对应指针后移
  4. 将剩余未遍历元素全部追加

✅ 完整代码（Java）

publicstaticint[]mergeSortedArrays(int[]arr1,int[]arr2){if(arr1==null)returnarr2;if(arr2==null)returnarr1;int[]result=newint[arr1.length+arr2.length];inti=0,j=0,k=0;while(i<arr1.length&&j<arr2.length){if(arr1[i]<=arr2[j]){result[k++]=arr1[i++];}else{result[k++]=arr2[j++];}}while(i<arr1.length)result[k++]=arr1[i++];while(j<arr2.length)result[k++]=arr2[j++];returnresult;}

⚠️ 期末易错点

• 忽略空数组边界条件（如arr1 == null）
• 结果数组长度错误（应为arr1.length + arr2.length）
• 遗漏处理剩余元素（导致部分数据丢失）

考点2：无序集合的交集与并集

📌 题目要求

给定两个可能含重复元素的无序数组，求交集（共同元素）和并集（所有元素去重）。

💡 实现思路

• 核心数据结构：HashSet（自动去重 + O(1) 查询）
• 交集：先存入 set1，再遍历 set2 筛选存在元素
• 并集：直接将两数组元素加入同一 HashSet

✅ 完整代码

// 交集publicstaticint[]findIntersection(int[]set1,int[]set2){Set<Integer>tempSet=newHashSet<>();Set<Integer>intersectionSet=newHashSet<>();for(intnum:set1)tempSet.add(num);for(intnum:set2){if(tempSet.contains(num))intersectionSet.add(num);}returnintersectionSet.stream().mapToInt(Integer::intValue).toArray();}// 并集publicstaticint[]findUnion(int[]set1,int[]set2){Set<Integer>unionSet=newHashSet<>();for(intnum:set1)unionSet.add(num);for(intnum:set2)unionSet.add(num);returnunionSet.stream().mapToInt(Integer::intValue).toArray();}

💡 提示：可使用stream().mapToInt()简化数组转换（考试若限制 JDK 版本，可用传统循环）

📊 复杂度分析

考点3：有序集合的交集与并集

📌 题目要求

两个非递减有序数组（可能含重复），求有序且无重复的交集与并集。

💡 实现思路

• 核心算法：双指针法（无需额外空间）
• 优势：利用有序性，避免使用 HashSet，空间复杂度 O(1)

✅ 完整代码

// 有序交集（去重）publicstaticint[]findSortedIntersection(int[]set1,int[]set2){List<Integer>res=newArrayList<>();inti=0,j=0;while(i<set1.length&&j<set2.length){if(set1[i]==set2[j]){if(res.isEmpty()||res.get(res.size()-1)!=set1[i]){res.add(set1[i]);}i++;j++;}elseif(set1[i]<set2[j]){i++;}else{j++;}}returnres.stream().mapToInt(Integer::intValue).toArray();}// 有序并集（去重）publicstaticint[]findSortedUnion(int[]set1,int[]set2){List<Integer>res=newArrayList<>();inti=0,j=0;while(i<set1.length&&j<set2.length){if(set1[i]<set2[j]){res.add(set1[i++]);}elseif(set1[i]>set2[j]){res.add(set2[j++]);}else{res.add(set1[i]);i++;j++;}}while(i<set1.length)res.add(set1[i++]);while(j<set2.length)res.add(set2[j++]);returnres.stream().mapToInt(Integer::intValue).toArray();}

🔥 期末高频考点

• 有序交集必须去重：即使输入有重复，输出只能保留一次
• 双指针移动逻辑：相等时同时移动，不等时移动较小者
• 对比无序解法：有序解法空间更优（O(1) vs O(n)）

考点4：字符数组拆分（数字/字母分类）

📌 题目要求

将数组{'1','g','3','4','e',...}拆分为数字字符数组和字母字符数组，保持原顺序。

💡 实现思路

1. 第一遍：统计数字和字母个数（确定结果数组长度）
2. 第二遍：分别填充两个结果数组
3. 注意：只处理'0'-'9'和'a'-'z'/'A'-'Z'

✅ 完整代码

publicstaticchar[][]splitArrayA(char[]arr){intnums=0,letters=0;for(charc:arr){if(c>='0'&&c<='9')nums++;elseif((c>='a'&&c<='z')||(c>='A'&&c<='Z'))letters++;}char[]numArr=newchar[nums];char[]letterArr=newchar[letters];intni=0,li=0;for(charc:arr){if(c>='0'&&c<='9'){numArr[ni++]=c;}elseif((c>='a'&&c<='z')||(c>='A'&&c<='Z')){letterArr[li++]=c;}}returnnewchar[][]{numArr,letterArr};}

⚠️ 易错点提醒

• 字符判断范围写错（如漏掉大写字母）
• 未先统计数量，直接创建固定长度数组 →数组越界
• 存储指针未自增 → 元素被覆盖

考点5：有序数组去重（两种算法对比）

📌 题目要求

对非递减有序数组去重（保留唯一元素），实现两种不同复杂度的算法。

✅ 算法1：双指针法（推荐！）

• 时间复杂度：O(n)
• 空间复杂度：O(1)（原地修改）
• 适用：数组有序 + 要求空间优化

publicstaticint[]removeDuplicatesByTwoPointers(int[]arr){if(arr==null||arr.length<=1)returnarr;intslow=0;for(intfast=1;fast<arr.length;fast++){if(arr[fast]!=arr[slow]){arr[++slow]=arr[fast];}}returnArrays.copyOf(arr,slow+1);}

✅ 算法2：LinkedHashSet 法

• 时间复杂度：O(n)
• 空间复杂度：O(n)
• 优点：代码简洁，自动去重 + 保序

publicstaticint[]removeDuplicatesByHashSet(int[]arr){Set<Integer>set=newLinkedHashSet<>();for(intx:arr)set.add(x);returnset.stream().mapToInt(Integer::intValue).toArray();}

📊 算法对比表

💡考试重点：理解“空间换时间” vs “时间换空间”的设计哲学！

三、期末复习总结

✅四大核心思想：

1. 有序性是优化关键：能用双指针就别用 HashSet
2. 双指针是数组操作的万金油：合并、去重、交并集都能用
3. 边界条件必检查：空数组、单元素、全重复等
4. 复杂度要会分析：时间 vs 空间权衡是高频简答题

✅三大易错雷区：

• 数组越界（长度计算错误、指针未移动）
• 忘记去重（尤其有序交集）
• 字符判断逻辑不全（大小写、数字范围）

✅代码规范建议：

• 方法命名清晰（如mergeSortedArrays）
• 添加必要注释（考试阅卷加分项）
• 处理null输入（体现健壮性）

四、完整测试代码（一键运行）

importjava.util.*;publicclassArrayFinalReview{publicstaticvoidmain(String[]args){System.out.println("===== 数组核心操作测试 =====");testMerge();System.out.println("------------------------------");testUnorderedSet();System.out.println("------------------------------");testSortedSet();System.out.println("------------------------------");testSplit();System.out.println("------------------------------");testRemoveDuplicates();}// 此处粘贴上述所有方法（略，实际使用时补全）}

结语
掌握这五大核心操作，你就已经覆盖了期末数组题型的 90%！建议动手敲一遍代码，理解每一步的逻辑，尤其是双指针的移动规则和去重时机。祝大家期末稳过，高分上岸！🎉

📌关注我，获取更多数据结构 & 算法期末复习干货！