企业官网建设流程全解析

建网站没有公司资质,中山网站开发费用,网络信息安全,单个网页打不开是什么原因问题描述给定一个有序的整数数组#xff0c;我们需要原地移除所有重复元素#xff0c;使得每个元素只出现一次#xff0c;并返回新数组的长度。要求不使用额外的数组空间#xff0c;空间复杂度为O(1)。示例#xff1a;输入#xff1a;nums [1,1,2,2,3,4,4,5] 输出#…问题描述给定一个有序的整数数组我们需要原地移除所有重复元素使得每个元素只出现一次并返回新数组的长度。要求不使用额外的数组空间空间复杂度为O(1)。示例输入nums [1,1,2,2,3,4,4,5] 输出5, nums [1,2,3,4,5,...]方法一HashSetHashSet是Java集合框架中的一个类它实现了Set接口底层基于哈希表实现。HashSet的核心特性是不允许重复元素且不保证元素的顺序。代码实现import java.util.HashSet; import java.util.Iterator; public class HashSetSolution { public int removeDuplicates(int[] nums) { // 边界条件检查 if (nums null || nums.length 0) { return 0; } // 创建HashSet存储唯一元素 HashSetInteger uniqueSet new HashSet(); // 遍历原数组将元素添加到HashSet中 // HashSet会自动去重重复元素不会被添加 for (int num : nums) { uniqueSet.add(num); } // 将Set中的元素复制回数组 // 注意HashSet不保证顺序所以结果可能不是有序的 int index 0; IteratorInteger iterator uniqueSet.iterator(); while (iterator.hasNext()) { nums[index] iterator.next(); } // 返回唯一元素的数量 return uniqueSet.size(); } }算法分析时间复杂度添加元素到HashSetO(n)遍历HashSetO(k)其中k是唯一元素的数量总时间复杂度O(n)空间复杂度HashSet需要存储所有唯一元素O(k) ≈ O(n)最坏情况优点代码简洁逻辑直观易于理解通用性强适用于无序数组的去重自动去重利用Java集合框架的特性缺点破坏顺序HashSet不保证元素的插入顺序对于有序数组会打乱原始顺序额外空间需要O(n)的额外空间不符合题目原地修改的要求性能开销哈希表操作有一定的开销包括哈希计算、处理哈希冲突等适用场景当数组无序且需要去重时当不关心元素顺序时当内存空间充足可以接受O(n)额外空间时方法二双指针法推荐双指针法是一种经典的原地算法技巧。我们使用两个指针快指针遍历整个数组寻找新的不重复元素慢指针指向下一个不重复元素应该存放的位置由于数组是有序的重复元素必然相邻我们可以利用这个特性高效去重。代码实现public class TwoPointerSolution { public int removeDuplicates(int[] nums) { // 边界条件检查 if (nums null || nums.length 0) { return 0; } // 慢指针指向下一个不重复元素应该存放的位置 // 初始为1因为第一个元素肯定不需要检查 int slow 1; // 快指针遍历整个数组 for (int fast 1; fast nums.length; fast) { // 如果当前元素不等于前一个元素说明找到了新的不重复元素 if (nums[fast] ! nums[fast - 1]) { // 将不重复元素复制到慢指针的位置 nums[slow] nums[fast]; // 慢指针前进 slow; } // 快指针始终前进 } // 慢指针的值就是新数组的长度 return slow; } // 更简洁的写法 public int removeDuplicatesConcise(int[] nums) { if (nums.length 0) return 0; int i 0; for (int j 1; j nums.length; j) { if (nums[j] ! nums[i]) { i; nums[i] nums[j]; } } return i 1; } }算法分析时间复杂度只需要遍历数组一次O(n)空间复杂度只使用了几个指针变量O(1)优点原地修改不需要额外空间符合题目要求保持顺序保持原始数组的有序性性能高效只需要一次遍历没有哈希计算开销内存友好适合处理大规模数据缺点仅适用于有序数组对于无序数组无效需要手动实现相比HashSet代码需要自己控制指针工作原理详解让我们通过一个例子来理解双指针法初始数组[1, 1, 2, 2, 3, 4, 4, 5]步骤初始化slow 1,fast 1fast1: nums[1]1, nums[0]1相等跳过fast2: nums[2]2, nums[1]1不相等复制到slow1slow2fast3: nums[3]2, nums[2]2相等跳过fast4: nums[4]3, nums[3]2不相等复制到slow2slow3以此类推...最终结果前5个元素为[1, 2, 3, 4, 5]返回5对比分析特性HashSet法双指针法时间复杂度O(n)O(n)空间复杂度O(n)O(1)是否保持顺序否是是否原地修改否是适用数组类型任意数组有序数组代码复杂度简单中等内存使用高低性能表现良好哈希计算开销优秀实际应用场景适合使用HashSet的场景处理日志去重日志数据通常无序且不关心顺序用户ID去重用户ID列表需要快速去重且顺序不重要数据预处理在数据清洗阶段需要快速识别和去重适合使用双指针的场景数据库查询结果去重数据库查询结果通常有序时间序列数据处理时间序列数据天然有序算法竞赛对内存和性能有严格要求嵌入式系统内存受限的环境变种问题与扩展问题变种保留最多k个重复元素javapublic int removeDuplicatesK(int[] nums, int k) { if (nums.length k) return nums.length; int slow k; // 前k个元素肯定保留 for (int fast k; fast nums.length; fast) { // 检查当前元素是否与slow-k位置的元素不同 if (nums[fast] ! nums[slow - k]) { nums[slow] nums[fast]; slow; } } return slow; }问题变种无序数组去重要求原地javapublic int removeDuplicatesUnordered(int[] nums) { // 先排序再使用双指针法 Arrays.sort(nums); return removeDuplicates(nums); }最佳实践建议分析问题特性首先判断数组是否有序考虑内存限制如果内存受限优先考虑双指针法考虑顺序要求如果需要保持顺序选择双指针法代码可读性在团队开发中选择易于理解和维护的方法性能需求对于性能敏感的场景进行基准测试总结在有序数组去重的问题中双指针法无疑是更优的选择。它不仅满足题目要求的原地修改和O(1)空间复杂度而且保持数组有序性能优异。虽然HashSet法代码更简洁但其破坏顺序和额外空间开销的缺点使其不适用于此问题。关键启示没有绝对最好的算法只有最适合特定场景的算法理解问题约束是选择算法的关键在面试中不仅要写出解决方案还要能解释为什么选择这种方法掌握这两种方法不仅能够解决有序数组去重问题还能为处理更复杂的数组操作问题打下坚实基础。在实际开发中根据具体需求选择合适的算法是每个开发者必备的技能。