企业官网建设流程全解析

网站被k怎么解决,外贸网站如何做推广是什么,做网站的需求清单,网站开发需要哪些知识LeetCode100天Day13-移除元素与多数元素#xff1a;双指针移除与排序计数 摘要#xff1a;本文详细解析了LeetCode中两道经典数组题目——“移除元素和多数元素”。通过双指针实现原地移除元素#xff0c;以及使用排序和计数查找多数元素#xff0c;帮助读者掌…LeetCode100天Day13-移除元素与多数元素双指针移除与排序计数摘要本文详细解析了LeetCode中两道经典数组题目——“移除元素和多数元素”。通过双指针实现原地移除元素以及使用排序和计数查找多数元素帮助读者掌握数组元素操作和查找的技巧。目录文章目录LeetCode100天Day13-移除元素与多数元素双指针移除与排序计数目录1. 移除元素Remove Element1.1 题目描述1.2 解题思路1.3 代码实现1.4 代码逐行解释第一部分初始化指针第二部分遍历数组1.5 执行流程详解1.6 算法图解1.7 复杂度分析1.8 边界情况2. 多数元素Majority Element2.1 题目描述2.2 解题思路2.3 代码实现2.4 代码逐行解释第一部分计算阈值第二部分排序第三部分统计计数2.5 执行流程详解2.6 算法图解2.7 复杂度分析2.8 边界情况3. 两题对比与总结3.1 算法对比3.2 双指针移除模板3.3 排序计数模板3.4 摩尔投票法3.5 整数除法陷阱4. 总结参考资源文章标签1. 移除元素Remove Element1.1 题目描述给你一个数组nums和一个值val你需要原地移除所有数值等于val的元素并返回移除后数组的新长度。不要使用额外的数组空间你必须仅使用 O(1) 额外空间并原地修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。示例 1输入nums [3,2,2,3], val 3 输出2, nums [2,2,_,_] 解释函数应该返回新的长度2并且nums中的前两个元素均为2。你不需要考虑数组中超出新长度后面的元素。示例 2输入nums [0,1,2,2,3,0,4,2], val 2 输出5, nums [0,1,3,0,4,_,_,_] 解释函数应该返回新的长度5并且nums中的前五个元素为0, 1, 3, 0, 4。注意这五个元素可以任意顺序。你不需要考虑数组中超出新长度后面的元素。1.2 解题思路这道题使用双指针的方法使用慢指针k指向下一个非val元素应该放置的位置使用快指针i遍历数组当遇到不等于val的元素时将其放到k的位置然后k返回k解题步骤初始化k0遍历数组检查每个元素如果当前元素不等于val将其放到nums[k]k返回k1.3 代码实现classSolution{publicintremoveElement(int[]nums,intval){intk0;for(inti0;inums.length;i){if(nums[i]!val){nums[k]nums[i];k;}}returnk;}}1.4 代码逐行解释第一部分初始化指针intk0;功能k是慢指针写指针指向下一个非val元素应该放置的位置初始值为0表示从数组开头开始写入第二部分遍历数组for(inti0;inums.length;i){if(nums[i]!val){nums[k]nums[i];k;}}指针说明指针作用说明i快指针读指针遍历整个数组k慢指针写指针指向写入位置判断逻辑if(nums[i]!val)条件操作nums[i] ! val保留元素写入nums[k]nums[i] val跳过不写入写入逻辑nums[k]nums[i];k;操作说明nums[k] nums[i]将非val元素复制到k位置k移动到下一个写入位置1.5 执行流程详解示例1nums [3,2,2,3], val 3初始状态 nums [3, 2, 2, 3] k 0 i0: nums[0] 3 3 ! 3? 否跳过 k 0 i1: nums[1] 2 2 ! 3? 是 nums[0] 2 nums [2, 2, 2, 3] k 1 i2: nums[2] 2 2 ! 3? 是 nums[1] 2 nums [2, 2, 2, 3] k 2 i3: nums[3] 3 3 ! 3? 否跳过 k 2 循环结束返回 k 2 最终数组前2个元素: [2, 2]示例2nums [0,1,2,2,3,0,4,2], val 2初始状态 nums [0, 1, 2, 2, 3, 0, 4, 2] k 0 i0: nums[0]0, 0 ! 2? 是 nums[0] 0, k 1 i1: nums[1]1, 1 ! 2? 是 nums[1] 1, k 2 i2: nums[2]2, 2 ! 2? 否跳过 i3: nums[3]2, 2 ! 2? 否跳过 i4: nums[4]3, 3 ! 2? 是 nums[2] 3, k 3 i5: nums[5]0, 0 ! 2? 是 nums[3] 0, k 4 i6: nums[6]4, 4 ! 2? 是 nums[4] 4, k 5 i7: nums[7]2, 2 ! 2? 否跳过 循环结束返回 k 5 最终数组前5个元素: [0, 1, 3, 0, 4]1.6 算法图解初始数组: [3, 2, 2, 3], val 3 索引: 0 1 2 3 步骤1: i0, k0 数组: [3, 2, 2, 3] 索引: ↑ i0, k0 nums[0] 3, 等于val跳过 步骤2: i1, k0 数组: [3, 2, 2, 3] 索引: ↑ ↑ k0 i1 nums[1] 2, 不等于val nums[0] 2 数组: [2, 2, 2, 3] k 1 步骤3: i2, k1 数组: [2, 2, 2, 3] 索引: ↑ ↑ k1 i2 nums[2] 2, 不等于val nums[1] 2 数组: [2, 2, 2, 3] k 2 步骤4: i3, k2 数组: [2, 2, 2, 3] 索引: ↑ ↑ k2 i3 nums[3] 3, 等于val跳过 最终结果: k 2 数组前2个元素: [2, 2]1.7 复杂度分析分析维度复杂度说明时间复杂度O(n)遍历数组一次空间复杂度O(1)只使用常数空间优化思路当遇到val时可以与数组末尾元素交换减少写入次数// 优化版本双指针从两端classSolution{publicintremoveElement(int[]nums,intval){intleft0;intrightnums.length-1;while(leftright){if(nums[left]val){nums[left]nums[right--];}else{left;}}returnleft;}}1.8 边界情况numsval说明输出[]1空数组0[1]1单个待删除0[1]2单个保留1[3,3,3]3全部删除0[1,2,3]4无需删除32. 多数元素Majority Element2.1 题目描述给定一个大小为n的数组nums返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋的元素。你可以假设数组是非空的并且给定的数组总是存在多数元素。示例 1输入nums [3,2,3] 输出3示例 2输入nums [2,2,1,1,1,2,2] 输出22.2 解题思路这道题使用排序和计数的方法对数组进行排序遍历排序后的数组统计每个连续元素的出现次数如果某个元素的出现次数大于n/2返回该元素解题步骤计算阈值compare n * 1.0 / 2对数组排序遍历数组统计每个元素的出现次数如果次数大于compare返回该元素2.3 代码实现importjava.util.*;classSolution{publicintmajorityElement(int[]nums){doublecomparenums.length*(1.0)/2;Arrays.sort(nums);inttempnums[0];intk0;intanswernums[0];for(inti0;inums.length;i){if(tempnums[i]){k;if(kcompare){answernums[i];}}else{tempnums[i];k1;}}returnanswer;}}2.4 代码逐行解释第一部分计算阈值doublecomparenums.length*(1.0)/2;功能计算多数元素的阈值nums.length计算compare33 * 1.0 / 21.577 * 1.0 / 23.5为什么要用1.0// 错误写法intcomparenums.length/2;// 整数除法7/2 3// 正确写法doublecomparenums.length*1.0/2;// 7.0 / 2 3.5第二部分排序Arrays.sort(nums);功能对数组进行升序排序排序前排序后[3, 2, 3][2, 3, 3][2, 2, 1, 1, 1, 2, 2][1, 1, 1, 2, 2, 2, 2]第三部分统计计数inttempnums[0];intk0;intanswernums[0];for(inti0;inums.length;i){if(tempnums[i]){k;if(kcompare){answernums[i];}}else{tempnums[i];k1;}}变量说明变量初始值作用tempnums[0]当前统计的元素k0当前元素的计数answernums[0]多数元素的结果统计逻辑if(tempnums[i]){k;// 相同计数加1if(kcompare){answernums[i];// 超过阈值记录答案}}else{tempnums[i];// 不同切换到新元素k1;// 重置计数}2.5 执行流程详解示例1nums [3,2,3]初始状态 nums [3, 2, 3] 排序后: nums [2, 3, 3] compare 3 * 1.0 / 2 1.5 temp nums[0] 2 k 0 answer 2 i0: nums[0] 2 temp(2) nums[0](2)? 是 k 1 1 1.5? 否 i1: nums[1] 3 temp(2) nums[1](3)? 否 temp 3 k 1 i2: nums[2] 3 temp(3) nums[2](3)? 是 k 2 2 1.5? 是 answer 3 循环结束返回 answer 3 输出: 3示例2nums [2,2,1,1,1,2,2]初始状态 nums [2, 2, 1, 1, 1, 2, 2] 排序后: nums [1, 1, 1, 2, 2, 2, 2] compare 7 * 1.0 / 2 3.5 temp 1 k 0 answer 1 i0: nums[0]1, temp1 1 1? 是 k 1 1 3.5? 否 i1: nums[1]1, temp1 1 1? 是 k 2 2 3.5? 否 i2: nums[2]1, temp1 1 1? 是 k 3 3 3.5? 否 i3: nums[3]2, temp1 1 2? 否 temp 2 k 1 i4: nums[4]2, temp2 2 2? 是 k 2 2 3.5? 否 i5: nums[5]2, temp2 2 2? 是 k 3 3 3.5? 否 i6: nums[6]2, temp2 2 2? 是 k 4 4 3.5? 是 answer 2 循环结束返回 answer 2 输出: 22.6 算法图解初始数组: [2, 2, 1, 1, 1, 2, 2] 排序后: [1, 1, 1, 2, 2, 2, 2] 阈值: 3.5 步骤1: i0, temp1, k0 数组: [1, 1, 1, 2, 2, 2, 2] 索引: ↑ i0 nums[0]1 temp1 k 1 1 3.5? 否 步骤2: i1, temp1, k1 数组: [1, 1, 1, 2, 2, 2, 2] 索引: ↑ i1 nums[1]1 temp1 k 2 2 3.5? 否 步骤3: i2, temp1, k2 数组: [1, 1, 1, 2, 2, 2, 2] 索引: ↑ i2 nums[2]1 temp1 k 3 3 3.5? 否 步骤4: i3, temp1, k3 数组: [1, 1, 1, 2, 2, 2, 2] 索引: ↑ i3 nums[3]2 ! temp1 temp 2 k 1 步骤5-7: 继续统计2 k 2, 3, 4 4 3.5? 是 answer 2 最终结果: 22.7 复杂度分析分析维度复杂度说明时间复杂度O(n log n)排序的复杂度空间复杂度O(1)取决于排序实现优化思路可以使用摩尔投票法优化到O(n)// 优化版本摩尔投票法classSolution{publicintmajorityElement(int[]nums){intcount0;Integercandidatenull;for(intnum:nums){if(count0){candidatenum;}count(numcandidate)?1:-1;}returncandidate;}}2.8 边界情况nums说明输出[1]单元素1[1,1]两元素1[1,2,1]交替出现1[2,2,1,1,1,2,2]复杂情况23. 两题对比与总结3.1 算法对比对比项移除元素多数元素核心算法双指针排序计数数据结构数组数组时间复杂度O(n)O(n log n)空间复杂度O(1)O(1)应用场景删除特定元素查找多数元素3.2 双指针移除模板// 双指针移除元素模板intk0;// 写指针for(inti0;inums.length;i){// 读指针if(nums[i]!target){// 保留条件nums[k]nums[i];}}returnk;3.3 排序计数模板// 排序计数模板Arrays.sort(array);Typecurrentarray[0];intcount0;for(inti0;iarray.length;i){if(array[i]current){count;if(countthreshold){returnarray[i];}}else{currentarray[i];count1;}}3.4 摩尔投票法核心思想不同元素相互抵消剩下的元素就是多数元素// 摩尔投票法模板intcount0;Typecandidatenull;for(Typenum:array){if(count0){candidatenum;}count(numcandidate)?1:-1;}returncandidate;投票过程数组: [2, 2, 1, 1, 1, 2, 2] num2: count0, candidate2, count1 num2: count1, candidate2, count2 num1: count2, candidate2, count1 (抵消) num1: count1, candidate2, count0 (抵消) num1: count0, candidate1, count1 num2: count1, candidate1, count0 (抵消) num2: count0, candidate2, count1 最终: candidate23.5 整数除法陷阱// 整数除法inta7/2;// a 3 (向下取整)// 浮点数除法doubleb7*1.0/2;// b 3.5// 比较时if(countn/2){// 错误7/23需要3// count4时才满足但实际需要3.5}if(countn*1.0/2){// 正确// count4时满足}4. 总结今天我们学习了两道数组操作题目移除元素掌握双指针移除特定元素理解原地修改的技巧多数元素掌握排序计数查找多数元素理解统计计数的逻辑核心收获双指针可以实现原地移除元素空间复杂度O(1)排序后相同元素会连续便于统计计数时注意整数除法的陷阱摩尔投票法是查找多数元素的高效方法练习建议尝试用双指针从两端优化移除元素学习摩尔投票法并实现思考如何找到出现次数前k多的元素参考资源LeetCode 中国站 - 移除元素LeetCode 中国站 - 多数元素双指针算法详解摩尔投票法文章标签#LeetCode #算法 #Java #数组 #双指针喜欢这篇文章吗别忘了点赞、收藏和分享你的支持是我创作的最大动力