苏州网站建设书生商友专业网页制作平台

苏州网站建设书生商友,专业网页制作平台,wordpress 面包插件,景点网站设计与制作数据结构期末复习#xff1a;数组核心操作全解析#xff08;含代码实现与复杂度分析#xff09;前言 在数据结构期末考试中#xff0c;数组作为最基础、最常考的数据结构之一#xff0c;其核心操作是高频考点。本文系统梳理了五大经典数组操作题型——合并、交并集、拆分、…数据结构期末复习数组核心操作全解析含代码实现与复杂度分析前言在数据结构期末考试中数组作为最基础、最常考的数据结构之一其核心操作是高频考点。本文系统梳理了五大经典数组操作题型——合并、交并集、拆分、去重等结合实验场景提供完整 Java 代码实现、时间/空间复杂度分析及易错点提醒助你高效备考稳拿高分一、复习核心考点清单两个有序数组合并双指针经典应用无序集合的交集与并集HashSet 去重特性有序集合的交集与并集利用有序性优化字符数组拆分数字/字母分类有序数组去重两种时间复杂度算法对比二、各考点详细解析含代码 思路考点1两个有序数组合并 题目要求将两个非递减有序数组合并为一个新的非递减有序数组要求时间复杂度最优。 实现思路核心算法双指针法避免冗余排序时间复杂度O(n m)步骤处理边界情况任一数组为空直接返回另一个初始化双指针i,j和结果指针k比较元素小者入结果数组对应指针后移将剩余未遍历元素全部追加✅ 完整代码Javapublicstaticint[]mergeSortedArrays(int[]arr1,int[]arr2){if(arr1null)returnarr2;if(arr2null)returnarr1;int[]resultnewint[arr1.lengtharr2.length];inti0,j0,k0;while(iarr1.lengthjarr2.length){if(arr1[i]arr2[j]){result[k]arr1[i];}else{result[k]arr2[j];}}while(iarr1.length)result[k]arr1[i];while(jarr2.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){SetIntegertempSetnewHashSet();SetIntegerintersectionSetnewHashSet();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){SetIntegerunionSetnewHashSet();for(intnum:set1)unionSet.add(num);for(intnum:set2)unionSet.add(num);returnunionSet.stream().mapToInt(Integer::intValue).toArray();} 提示可使用stream().mapToInt()简化数组转换考试若限制 JDK 版本可用传统循环 复杂度分析操作时间复杂度空间复杂度交集O(n m)O(n)并集O(n m)O(n m)考点3有序集合的交集与并集 题目要求两个非递减有序数组可能含重复求有序且无重复的交集与并集。 实现思路核心算法双指针法无需额外空间优势利用有序性避免使用 HashSet空间复杂度 O(1)✅ 完整代码// 有序交集去重publicstaticint[]findSortedIntersection(int[]set1,int[]set2){ListIntegerresnewArrayList();inti0,j0;while(iset1.lengthjset2.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){ListIntegerresnewArrayList();inti0,j0;while(iset1.lengthjset2.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(iset1.length)res.add(set1[i]);while(jset2.length)res.add(set2[j]);returnres.stream().mapToInt(Integer::intValue).toArray();} 期末高频考点有序交集必须去重即使输入有重复输出只能保留一次双指针移动逻辑相等时同时移动不等时移动较小者对比无序解法有序解法空间更优O(1) vs O(n)考点4字符数组拆分数字/字母分类 题目要求将数组{1,g,3,4,e,...}拆分为数字字符数组和字母字符数组保持原顺序。 实现思路第一遍统计数字和字母个数确定结果数组长度第二遍分别填充两个结果数组注意只处理0-9和a-z/A-Z✅ 完整代码publicstaticchar[][]splitArrayA(char[]arr){intnums0,letters0;for(charc:arr){if(c0c9)nums;elseif((cacz)||(cAcZ))letters;}char[]numArrnewchar[nums];char[]letterArrnewchar[letters];intni0,li0;for(charc:arr){if(c0c9){numArr[ni]c;}elseif((cacz)||(cAcZ)){letterArr[li]c;}}returnnewchar[][]{numArr,letterArr};}⚠️ 易错点提醒字符判断范围写错如漏掉大写字母未先统计数量直接创建固定长度数组 →数组越界存储指针未自增 → 元素被覆盖考点5有序数组去重两种算法对比 题目要求对非递减有序数组去重保留唯一元素实现两种不同复杂度的算法。✅ 算法1双指针法推荐时间复杂度O(n)空间复杂度O(1)原地修改适用数组有序 要求空间优化publicstaticint[]removeDuplicatesByTwoPointers(int[]arr){if(arrnull||arr.length1)returnarr;intslow0;for(intfast1;fastarr.length;fast){if(arr[fast]!arr[slow]){arr[slow]arr[fast];}}returnArrays.copyOf(arr,slow1);}✅ 算法2LinkedHashSet 法时间复杂度O(n)空间复杂度O(n)优点代码简洁自动去重 保序publicstaticint[]removeDuplicatesByHashSet(int[]arr){SetIntegersetnewLinkedHashSet();for(intx:arr)set.add(x);returnset.stream().mapToInt(Integer::intValue).toArray();} 算法对比表算法时间复杂度空间复杂度是否原地适用场景双指针法O(n)O(1)✅有序数组、内存受限HashSet 法O(n)O(n)❌无序也可用、追求开发效率考试重点理解“空间换时间” vs “时间换空间”的设计哲学三、期末复习总结✅四大核心思想有序性是优化关键能用双指针就别用 HashSet双指针是数组操作的万金油合并、去重、交并集都能用边界条件必检查空数组、单元素、全重复等复杂度要会分析时间 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%建议动手敲一遍代码理解每一步的逻辑尤其是双指针的移动规则和去重时机。祝大家期末稳过高分上岸关注我获取更多数据结构 算法期末复习干货