九江市网站建设_网站建设公司_Node.js_seo优化

LeetCode100天Day13-移除元素与多数元素：双指针移除与排序计数

摘要：本文详细解析了LeetCode中两道经典数组题目——“移除元素"和"多数元素”。通过双指针实现原地移除元素，以及使用排序和计数查找多数元素，帮助读者掌握数组元素操作和查找的技巧。

目录

1. 移除元素（Remove Element）

1.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 解题思路

这道题使用双指针的方法：

1. 使用慢指针k指向下一个非val元素应该放置的位置
2. 使用快指针i遍历数组
3. 当遇到不等于val的元素时，将其放到k的位置，然后k++
4. 返回k

解题步骤：

1. 初始化k=0
2. 遍历数组，检查每个元素
3. 如果当前元素不等于val，将其放到nums[k]，k++
4. 返回k

1.3 代码实现

classSolution{publicintremoveElement(int[]nums,intval){intk=0;for(inti=0;i<nums.length;i++){if(nums[i]!=val){nums[k]=nums[i];k++;}}returnk;}}

1.4 代码逐行解释

第一部分：初始化指针

intk=0;

功能：

• k是慢指针（写指针），指向下一个非val元素应该放置的位置
• 初始值为0，表示从数组开头开始写入

第二部分：遍历数组

for(inti=0;i<nums.length;i++){if(nums[i]!=val){nums[k]=nums[i];k++;}}

指针说明：

判断逻辑：

if(nums[i]!=val)

写入逻辑：

nums[k]=nums[i];k++;

1.5 执行流程详解

示例1：nums = [3,2,2,3], val = 3

初始状态： nums = [3, 2, 2, 3] k = 0 i=0: nums[0] = 3 3 != 3? 否，跳过 k = 0 i=1: nums[1] = 2 2 != 3? 是 nums[0] = 2 nums = [2, 2, 2, 3] k = 1 i=2: nums[2] = 2 2 != 3? 是 nums[1] = 2 nums = [2, 2, 2, 3] k = 2 i=3: nums[3] = 3 3 != 3? 否，跳过 k = 2 循环结束，返回 k = 2 最终数组前2个元素: [2, 2]

示例2：nums = [0,1,2,2,3,0,4,2], val = 2

初始状态： nums = [0, 1, 2, 2, 3, 0, 4, 2] k = 0 i=0: nums[0]=0, 0 != 2? 是 nums[0] = 0, k = 1 i=1: nums[1]=1, 1 != 2? 是 nums[1] = 1, k = 2 i=2: nums[2]=2, 2 != 2? 否，跳过 i=3: nums[3]=2, 2 != 2? 否，跳过 i=4: nums[4]=3, 3 != 2? 是 nums[2] = 3, k = 3 i=5: nums[5]=0, 0 != 2? 是 nums[3] = 0, k = 4 i=6: nums[6]=4, 4 != 2? 是 nums[4] = 4, k = 5 i=7: 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: i=0, k=0 数组: [3, 2, 2, 3] 索引: ↑ i=0, k=0 nums[0] = 3, 等于val，跳过 步骤2: i=1, k=0 数组: [3, 2, 2, 3] 索引: ↑ ↑ k=0 i=1 nums[1] = 2, 不等于val nums[0] = 2 数组: [2, 2, 2, 3] k = 1 步骤3: i=2, k=1 数组: [2, 2, 2, 3] 索引: ↑ ↑ k=1 i=2 nums[2] = 2, 不等于val nums[1] = 2 数组: [2, 2, 2, 3] k = 2 步骤4: i=3, k=2 数组: [2, 2, 2, 3] 索引: ↑ ↑ k=2 i=3 nums[3] = 3, 等于val，跳过 最终结果: k = 2 数组前2个元素: [2, 2]

1.7 复杂度分析

优化思路：当遇到val时，可以与数组末尾元素交换，减少写入次数

// 优化版本：双指针从两端classSolution{publicintremoveElement(int[]nums,intval){intleft=0;intright=nums.length-1;while(left<=right){if(nums[left]==val){nums[left]=nums[right--];}else{left++;}}returnleft;}}

1.8 边界情况

2. 多数元素（Majority Element）

2.1 题目描述

给定一个大小为n的数组nums，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3] 输出：3

示例 2：

输入：nums = [2,2,1,1,1,2,2] 输出：2

2.2 解题思路

这道题使用排序和计数的方法：

1. 对数组进行排序
2. 遍历排序后的数组，统计每个连续元素的出现次数
3. 如果某个元素的出现次数大于n/2，返回该元素

解题步骤：

1. 计算阈值compare = n * 1.0 / 2
2. 对数组排序
3. 遍历数组，统计每个元素的出现次数
4. 如果次数大于compare，返回该元素

2.3 代码实现

importjava.util.*;classSolution{publicintmajorityElement(int[]nums){doublecompare=nums.length*(1.0)/2;Arrays.sort(nums);inttemp=nums[0];intk=0;intanswer=nums[0];for(inti=0;i<nums.length;i++){if(temp==nums[i]){k++;if(k>compare){answer=nums[i];}}else{temp=nums[i];k=1;}}returnanswer;}}

2.4 代码逐行解释

第一部分：计算阈值

doublecompare=nums.length*(1.0)/2;

功能：计算多数元素的阈值

为什么要用1.0：

// 错误写法intcompare=nums.length/2;// 整数除法，7/2 = 3// 正确写法doublecompare=nums.length*1.0/2;// 7.0 / 2 = 3.5

第二部分：排序

Arrays.sort(nums);

功能：对数组进行升序排序

第三部分：统计计数

inttemp=nums[0];intk=0;intanswer=nums[0];for(inti=0;i<nums.length;i++){if(temp==nums[i]){k++;if(k>compare){answer=nums[i];}}else{temp=nums[i];k=1;}}

变量说明：

统计逻辑：

if(temp==nums[i]){k++;// 相同，计数加1if(k>compare){answer=nums[i];// 超过阈值，记录答案}}else{temp=nums[i];// 不同，切换到新元素k=1;// 重置计数}

2.5 执行流程详解

示例1：nums = [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 i=0: nums[0] = 2 temp(2) == nums[0](2)? 是 k = 1 1 > 1.5? 否 i=1: nums[1] = 3 temp(2) == nums[1](3)? 否 temp = 3 k = 1 i=2: nums[2] = 3 temp(3) == nums[2](3)? 是 k = 2 2 > 1.5? 是 answer = 3 循环结束，返回 answer = 3 输出: 3

示例2：nums = [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 i=0: nums[0]=1, temp=1 1 == 1? 是 k = 1 1 > 3.5? 否 i=1: nums[1]=1, temp=1 1 == 1? 是 k = 2 2 > 3.5? 否 i=2: nums[2]=1, temp=1 1 == 1? 是 k = 3 3 > 3.5? 否 i=3: nums[3]=2, temp=1 1 == 2? 否 temp = 2 k = 1 i=4: nums[4]=2, temp=2 2 == 2? 是 k = 2 2 > 3.5? 否 i=5: nums[5]=2, temp=2 2 == 2? 是 k = 3 3 > 3.5? 否 i=6: nums[6]=2, temp=2 2 == 2? 是 k = 4 4 > 3.5? 是 answer = 2 循环结束，返回 answer = 2 输出: 2

2.6 算法图解

初始数组: [2, 2, 1, 1, 1, 2, 2] 排序后: [1, 1, 1, 2, 2, 2, 2] 阈值: 3.5 步骤1: i=0, temp=1, k=0 数组: [1, 1, 1, 2, 2, 2, 2] 索引: ↑ i=0 nums[0]=1 == temp=1 k = 1 1 > 3.5? 否 步骤2: i=1, temp=1, k=1 数组: [1, 1, 1, 2, 2, 2, 2] 索引: ↑ i=1 nums[1]=1 == temp=1 k = 2 2 > 3.5? 否 步骤3: i=2, temp=1, k=2 数组: [1, 1, 1, 2, 2, 2, 2] 索引: ↑ i=2 nums[2]=1 == temp=1 k = 3 3 > 3.5? 否 步骤4: i=3, temp=1, k=3 数组: [1, 1, 1, 2, 2, 2, 2] 索引: ↑ i=3 nums[3]=2 != temp=1 temp = 2 k = 1 步骤5-7: 继续统计2 k = 2, 3, 4 4 > 3.5? 是 answer = 2 最终结果: 2

2.7 复杂度分析

优化思路：可以使用摩尔投票法优化到O(n)

// 优化版本：摩尔投票法classSolution{publicintmajorityElement(int[]nums){intcount=0;Integercandidate=null;for(intnum:nums){if(count==0){candidate=num;}count+=(num==candidate)?1:-1;}returncandidate;}}

2.8 边界情况

3. 两题对比与总结

3.1 算法对比

3.2 双指针移除模板

// 双指针移除元素模板intk=0;// 写指针for(inti=0;i<nums.length;i++){// 读指针if(nums[i]!=target){// 保留条件nums[k++]=nums[i];}}returnk;

3.3 排序+计数模板

// 排序+计数模板Arrays.sort(array);Typecurrent=array[0];intcount=0;for(inti=0;i<array.length;i++){if(array[i]==current){count++;if(count>threshold){returnarray[i];}}else{current=array[i];count=1;}}

3.4 摩尔投票法

核心思想：

• 不同元素相互抵消
• 剩下的元素就是多数元素

// 摩尔投票法模板intcount=0;Typecandidate=null;for(Typenum:array){if(count==0){candidate=num;}count+=(num==candidate)?1:-1;}returncandidate;

投票过程：

数组: [2, 2, 1, 1, 1, 2, 2] num=2: count=0, candidate=2, count=1 num=2: count=1, candidate=2, count=2 num=1: count=2, candidate=2, count=1 (抵消) num=1: count=1, candidate=2, count=0 (抵消) num=1: count=0, candidate=1, count=1 num=2: count=1, candidate=1, count=0 (抵消) num=2: count=0, candidate=2, count=1 最终: candidate=2

3.5 整数除法陷阱

// 整数除法inta=7/2;// a = 3 (向下取整)// 浮点数除法doubleb=7*1.0/2;// b = 3.5// 比较时if(count>n/2){// 错误：7/2=3，需要>3// count=4时才满足，但实际需要>3.5}if(count>n*1.0/2){// 正确// count=4时满足}

4. 总结

今天我们学习了两道数组操作题目：

1. 移除元素：掌握双指针移除特定元素，理解原地修改的技巧
2. 多数元素：掌握排序+计数查找多数元素，理解统计计数的逻辑

核心收获：

• 双指针可以实现原地移除元素，空间复杂度O(1)
• 排序后相同元素会连续，便于统计
• 计数时注意整数除法的陷阱
• 摩尔投票法是查找多数元素的高效方法

练习建议：

1. 尝试用双指针从两端优化移除元素
2. 学习摩尔投票法并实现
3. 思考如何找到出现次数前k多的元素

参考资源

• LeetCode 中国站 - 移除元素
• LeetCode 中国站 - 多数元素
• 双指针算法详解
• 摩尔投票法

文章标签

#LeetCode #算法 #Java #数组 #双指针

喜欢这篇文章吗？别忘了点赞、收藏和分享！你的支持是我创作的最大动力！