尧图网页设计 
LeetCode 26. Remove Duplicates from Sorted ArrayGo 双指针原地去重题解【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 26 题 Remove Duplicates from Sorted Array删除有序数组中的重复项展开以本仓库 LeetCode-Go 中 0026 题解源码 与 单元测试 为证据完整还原问题约束、两种 Go 实现思路双指针快慢覆盖 / 借助 removeElement 交换去重以及测试用例设计。读完本文你将掌握原地修改 O(1) 额外空间去重这一类问题的通用解法并理解它与仓库中 27 题删除指定元素、283 题移动零之间的同构关系。题目理解返回值是长度数组却被改了Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.题目要求对已有序的数组nums原地去重使每个元素只保留一份并返回去重后的新长度。两个硬性约束原地修改不能新建数组承载结果O(1) 额外空间除输入数组本身外几乎不允许使用与输入规模相关的辅助存储。示例 1Given nums [1,1,2], Your function should return length 2, with the first two elements of nums being 1 and 2 respectively. It doesnt matter what you leave beyond the returned length.示例 2Given nums [0,0,1,1,1,2,2,3,3,4], Your function should return length 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively. It doesnt matter what values are set beyond the returned length.注意两句 It doesnt matter...返回长度之后的数组元素可以是任意残留值判题器只读取前len个元素。为什么返回值是整数而不是数组原题 Clarification 解释输入数组是按引用传递的函数内对数组的修改调用方可见。判题逻辑等价于// nums is passed in by reference. (i.e., without making a copy) int len removeElement(nums, val); // any modification to nums in your function would be known by the caller. // using the length returned by your function, it prints the first len elements. for (int i 0; i len; i) { print(nums[i]); }这正是 Go 语言切片的天然行为——切片头部包含指向底层数组的指针函数内对切片元素赋值会直接影响调用方的底层数组。解题思路删除不是真删除而是往前搬原文档明确指出这里的删除并不是真正删除元素而是把不需要保留的元素通过交换/覆盖移动到数组后面的空间然后返回实际剩余元素的个数OJ 最终只读取前len个元素。因此解题只需保证去重后的前 k 个位置依次存放 0..k-1 个互不相同的元素。题目总结Problem Summary可概括为给定有序数组nums去重使每个元素只出现一次返回去重后的数组长度。原文档还点明本题与仓库中另外两道题的高度同构题目核心操作仓库源码283. Move Zeroes把数组中的 0 移到末尾moveZeroes(nums []int)27. Remove Element删除指定值valremoveElement(nums []int, val int) int26. Remove Duplicates from Sorted Array删除重复元素removeDuplicates(nums []int) int三者在本质上都是双指针原地筛选只是筛选条件分别是非 0、不等于 val、与前一个不重复。解法一双指针快慢覆盖推荐这是仓库中编号为解法一的实现位于 26. Remove Duplicates from Sorted Array.gopackage leetcode // Solution 1 func removeDuplicates(nums []int) int { if len(nums) 0 { return 0 } last, finder : 0, 0 for last len(nums)-1 { for nums[finder] nums[last] { finder if finder len(nums) { return last 1 } } nums[last1] nums[finder] last } return last 1 }指针语义last已整理区间的末尾下标。nums[0..last]始终互不相同是去重结果的最终形态finder向前扫描的探测器负责寻找下一个与nums[last]不同的元素。执行流程空数组直接返回 0外层循环条件last len(nums)-1保证last1不会越界内层循环让finder跳过所有与nums[last]相等的元素若finder已越界说明剩余元素全部与nums[last]相同此时last1就是去重长度直接返回找到不同元素后将其覆盖到nums[last1]last前进一位。以[0,0,1,1,1,2,2,3,3,4]为例步骤lastfindernums 状态前段初始00[0, 0, 1, 1, 1, 2, 2, 3, 3, 4]跳过重复 002同上覆盖12[0, 1, 1, 1, 1, 2, 2, 3, 3, 4]跳过重复 115同上覆盖25[0, 1, 2, 1, 1, 2, 2, 3, 3, 4]…………结束410[0, 1, 2, 3, 4, 2, 2, 3, 3, 4]最终返回last1 5前 5 位恰好是0,1,2,3,4符合示例 2 的预期输出。复杂度时间复杂度 O(n)finder全程单调递增每个元素最多被扫描一次空间复杂度 O(1)仅使用两个整型指针变量。解法二借助 removeElement 的搬运式去重仓库解法二换了一个角度既然删除元素本质上就是把不等于某值的元素往前交换那么可以复用类似 27 题 removeElement 的交换逻辑。实现在 26. Remove Duplicates from Sorted Array.go// Solution 2 func removeDuplicates1(nums []int) int { if len(nums) 0 { return 0 } length : len(nums) lastNum : nums[length-1] i : 0 for i 0; i length-1; i { if nums[i] lastNum { break } if nums[i1] nums[i] { removeElement1(nums, i1, nums[i]) // fmt.Printf(At this point num %v length %v\n, nums, length) } } return i 1 } func removeElement1(nums []int, start, val int) int { if len(nums) 0 { return 0 } j : start for i : start; i len(nums); i { if nums[i] ! val { if i ! j { nums[i], nums[j] nums[j], nums[i] j } else { j } } } return j }设计要点先用lastNum : nums[length-1]记录末尾元素作为哨兵由于数组有序一旦某个位置的值等于lastNum说明从该位置起全是最大值不可能再有新元素立即break从左到右扫描每当发现nums[i1] nums[i]出现重复就从i1位置开始调用removeElement1把等于nums[i]的重复值全部交换到尾部removeElement1采用与 27 题相同的双指针交换模式j是写入位i是扫描位遇到不等于val的元素就与j处交换i j时等价于原地自写只推进j。该解法借助已封装的removeElement1让思路与 27 题统一但每次调用都会把一段重复值搬运到末尾最坏情况下的交换次数比解法一更多因此在仓库中作为解法二呈现用于展示同一问题不同抽象层次的解法。测试验证仓库是如何保证 100% 覆盖率的仓库以100% test coverage为口号本题的验证位于 26. Remove Duplicates from Sorted Array_test.go测试表驱动用例覆盖了输入期望长度覆盖场景[]0空数组边界[1,1,2]2题目示例 1[0,0,1,1,1,1,2,3,4,4]5多重连续重复 末尾重复[0,0,0,0,0]1全数组为同一元素内层 finder 越界提前返回[1]1单元素数组测试中还做了两处值得一提的设计clone26深拷贝输入因为两个解法都是原地修改必须先拷贝原切片再分别调用避免前一个解法的修改污染后一个解法的输入直接单测removeElement1辅助函数显式验证空输入返回 0、以及i j与i ! j两个分支如removeElement1([]int{2, 1, 3, 1, 4}, 0, 1) ! 3会触发t.Fatalf这正是仓库实现行级 100% 覆盖率的典型手段。在已安装 Go 工具链且配置好模块依赖的环境下可运行go test ./leetcode/0026.Remove-Duplicates-from-Sorted-Array/ -v -run Test_Problem26仓库根目录还提供了 gotest.sh其中使用go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...一次性生成统一的覆盖率报告coverage.txt供持续集成CI统计整仓覆盖率。关联题目横向对比一套双指针走天下题目筛选条件返回对应源码283. Move Zeroesnums[i] ! 0无原地整理283. Move Zeroes.go27. Remove Elementnums[i] ! val剩余长度27. Remove Element.go26. Remove Duplicatesnums[i] ! nums[last]有序前提下与前一个比较去重长度26. Remove Duplicates from Sorted Array.go对比可见27 题的removeElement使用了最标准的快慢双指针 条件交换模板j为写入位、i为扫描位i ! j时交换并推进j283 题moveZeroes与其完全同构只是条件变为nums[i] ! 0而 26 题的解法二正是把 27 题的模板内嵌为辅助函数removeElement1。把这三道题放在一起练习可以一次性吃透原地删除/去重/移动三类高频面试题。总结题目本质有序数组原地去重返回值是去重后长度长度之后的内容不做要求核心约束原地修改 O(1) 额外空间杜绝新建数组解法一双指针覆盖last维护已整理区finder跳过重复值时间 O(n)、空间 O(1)实现最简洁推荐掌握解法二搬运式借助removeElement1把重复值交换到尾部与 27 题解题框架统一便于横向迁移验证方式仓库配套表驱动测试覆盖空数组、单元素、全重复、多重连续重复等边界并直接单测辅助函数以支撑 100% 覆盖率。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 26. Remove Duplicates from Sorted Array：Go 双指针原地去重题解
LeetCode 26. Remove Duplicates from Sorted ArrayGo 双指针原地去重题解【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 26 题 Remove Duplicates from Sorted Array删除有序数组中的重复项展开以本仓库 LeetCode-Go 中 0026 题解源码 与 单元测试 为证据完整还原问题约束、两种 Go 实现思路双指针快慢覆盖 / 借助 removeElement 交换去重以及测试用例设计。读完本文你将掌握原地修改 O(1) 额外空间去重这一类问题的通用解法并理解它与仓库中 27 题删除指定元素、283 题移动零之间的同构关系。题目理解返回值是长度数组却被改了Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.题目要求对已有序的数组nums原地去重使每个元素只保留一份并返回去重后的新长度。两个硬性约束原地修改不能新建数组承载结果O(1) 额外空间除输入数组本身外几乎不允许使用与输入规模相关的辅助存储。示例 1Given nums [1,1,2], Your function should return length 2, with the first two elements of nums being 1 and 2 respectively. It doesnt matter what you leave beyond the returned length.示例 2Given nums [0,0,1,1,1,2,2,3,3,4], Your function should return length 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively. It doesnt matter what values are set beyond the returned length.注意两句 It doesnt matter...返回长度之后的数组元素可以是任意残留值判题器只读取前len个元素。为什么返回值是整数而不是数组原题 Clarification 解释输入数组是按引用传递的函数内对数组的修改调用方可见。判题逻辑等价于// nums is passed in by reference. (i.e., without making a copy) int len removeElement(nums, val); // any modification to nums in your function would be known by the caller. // using the length returned by your function, it prints the first len elements. for (int i 0; i len; i) { print(nums[i]); }这正是 Go 语言切片的天然行为——切片头部包含指向底层数组的指针函数内对切片元素赋值会直接影响调用方的底层数组。解题思路删除不是真删除而是往前搬原文档明确指出这里的删除并不是真正删除元素而是把不需要保留的元素通过交换/覆盖移动到数组后面的空间然后返回实际剩余元素的个数OJ 最终只读取前len个元素。因此解题只需保证去重后的前 k 个位置依次存放 0..k-1 个互不相同的元素。题目总结Problem Summary可概括为给定有序数组nums去重使每个元素只出现一次返回去重后的数组长度。原文档还点明本题与仓库中另外两道题的高度同构题目核心操作仓库源码283. Move Zeroes把数组中的 0 移到末尾moveZeroes(nums []int)27. Remove Element删除指定值valremoveElement(nums []int, val int) int26. Remove Duplicates from Sorted Array删除重复元素removeDuplicates(nums []int) int三者在本质上都是双指针原地筛选只是筛选条件分别是非 0、不等于 val、与前一个不重复。解法一双指针快慢覆盖推荐这是仓库中编号为解法一的实现位于 26. Remove Duplicates from Sorted Array.gopackage leetcode // Solution 1 func removeDuplicates(nums []int) int { if len(nums) 0 { return 0 } last, finder : 0, 0 for last len(nums)-1 { for nums[finder] nums[last] { finder if finder len(nums) { return last 1 } } nums[last1] nums[finder] last } return last 1 }指针语义last已整理区间的末尾下标。nums[0..last]始终互不相同是去重结果的最终形态finder向前扫描的探测器负责寻找下一个与nums[last]不同的元素。执行流程空数组直接返回 0外层循环条件last len(nums)-1保证last1不会越界内层循环让finder跳过所有与nums[last]相等的元素若finder已越界说明剩余元素全部与nums[last]相同此时last1就是去重长度直接返回找到不同元素后将其覆盖到nums[last1]last前进一位。以[0,0,1,1,1,2,2,3,3,4]为例步骤lastfindernums 状态前段初始00[0, 0, 1, 1, 1, 2, 2, 3, 3, 4]跳过重复 002同上覆盖12[0, 1, 1, 1, 1, 2, 2, 3, 3, 4]跳过重复 115同上覆盖25[0, 1, 2, 1, 1, 2, 2, 3, 3, 4]…………结束410[0, 1, 2, 3, 4, 2, 2, 3, 3, 4]最终返回last1 5前 5 位恰好是0,1,2,3,4符合示例 2 的预期输出。复杂度时间复杂度 O(n)finder全程单调递增每个元素最多被扫描一次空间复杂度 O(1)仅使用两个整型指针变量。解法二借助 removeElement 的搬运式去重仓库解法二换了一个角度既然删除元素本质上就是把不等于某值的元素往前交换那么可以复用类似 27 题 removeElement 的交换逻辑。实现在 26. Remove Duplicates from Sorted Array.go// Solution 2 func removeDuplicates1(nums []int) int { if len(nums) 0 { return 0 } length : len(nums) lastNum : nums[length-1] i : 0 for i 0; i length-1; i { if nums[i] lastNum { break } if nums[i1] nums[i] { removeElement1(nums, i1, nums[i]) // fmt.Printf(At this point num %v length %v\n, nums, length) } } return i 1 } func removeElement1(nums []int, start, val int) int { if len(nums) 0 { return 0 } j : start for i : start; i len(nums); i { if nums[i] ! val { if i ! j { nums[i], nums[j] nums[j], nums[i] j } else { j } } } return j }设计要点先用lastNum : nums[length-1]记录末尾元素作为哨兵由于数组有序一旦某个位置的值等于lastNum说明从该位置起全是最大值不可能再有新元素立即break从左到右扫描每当发现nums[i1] nums[i]出现重复就从i1位置开始调用removeElement1把等于nums[i]的重复值全部交换到尾部removeElement1采用与 27 题相同的双指针交换模式j是写入位i是扫描位遇到不等于val的元素就与j处交换i j时等价于原地自写只推进j。该解法借助已封装的removeElement1让思路与 27 题统一但每次调用都会把一段重复值搬运到末尾最坏情况下的交换次数比解法一更多因此在仓库中作为解法二呈现用于展示同一问题不同抽象层次的解法。测试验证仓库是如何保证 100% 覆盖率的仓库以100% test coverage为口号本题的验证位于 26. Remove Duplicates from Sorted Array_test.go测试表驱动用例覆盖了输入期望长度覆盖场景[]0空数组边界[1,1,2]2题目示例 1[0,0,1,1,1,1,2,3,4,4]5多重连续重复 末尾重复[0,0,0,0,0]1全数组为同一元素内层 finder 越界提前返回[1]1单元素数组测试中还做了两处值得一提的设计clone26深拷贝输入因为两个解法都是原地修改必须先拷贝原切片再分别调用避免前一个解法的修改污染后一个解法的输入直接单测removeElement1辅助函数显式验证空输入返回 0、以及i j与i ! j两个分支如removeElement1([]int{2, 1, 3, 1, 4}, 0, 1) ! 3会触发t.Fatalf这正是仓库实现行级 100% 覆盖率的典型手段。在已安装 Go 工具链且配置好模块依赖的环境下可运行go test ./leetcode/0026.Remove-Duplicates-from-Sorted-Array/ -v -run Test_Problem26仓库根目录还提供了 gotest.sh其中使用go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...一次性生成统一的覆盖率报告coverage.txt供持续集成CI统计整仓覆盖率。关联题目横向对比一套双指针走天下题目筛选条件返回对应源码283. Move Zeroesnums[i] ! 0无原地整理283. Move Zeroes.go27. Remove Elementnums[i] ! val剩余长度27. Remove Element.go26. Remove Duplicatesnums[i] ! nums[last]有序前提下与前一个比较去重长度26. Remove Duplicates from Sorted Array.go对比可见27 题的removeElement使用了最标准的快慢双指针 条件交换模板j为写入位、i为扫描位i ! j时交换并推进j283 题moveZeroes与其完全同构只是条件变为nums[i] ! 0而 26 题的解法二正是把 27 题的模板内嵌为辅助函数removeElement1。把这三道题放在一起练习可以一次性吃透原地删除/去重/移动三类高频面试题。总结题目本质有序数组原地去重返回值是去重后长度长度之后的内容不做要求核心约束原地修改 O(1) 额外空间杜绝新建数组解法一双指针覆盖last维护已整理区finder跳过重复值时间 O(n)、空间 O(1)实现最简洁推荐掌握解法二搬运式借助removeElement1把重复值交换到尾部与 27 题解题框架统一便于横向迁移验证方式仓库配套表驱动测试覆盖空数组、单元素、全重复、多重连续重复等边界并直接单测辅助函数以支撑 100% 覆盖率。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考