26. 删除有序数组中的重复项
用二分法定位数组中的元素
26.题目链接-来源:力扣(LeetCode)
给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。
不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1:
输入:nums = [1,1,2]
输出:2, nums = [1,2]
解释:函数应该返回新的长度 2 ,并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
思路:
我们可以跳跃地处理数组的数据。容易想象,对于处理完毕的结果数组,在有效长度(即返回值对应的长度)内,每一个元素的值都不相等。我们只要跳跃地取出这些值,依次复制到数组头部,待跳跃超出了数组实际长度后停止即可。
由于数组有序,容易想到用二分法来定位待操作的元素。
我们可以写一个辅助函数 findNextEle(target),这个函数的作用是返回 「数组中大于 target 的第一个元素」。对于数组中的第一个元素,我们令 target = nums[0],调用 findNextEle() 即可找到下一个要复制的元素所在的位置,也就是我们跳转的目标。于是我们依次在数组的第 i 位,放下 第 findNextEle(num[i]) 个元素,即可完成目标。
于是我们只要实现这个 findNextEle() 函数即可。主体结构是二分法,在数组中,用两个指针 l 和 r 指明查找的边界,比较边界中点 mid 处指向的值,若小于等于待查找元素 target,则右移 l,否则左移 r,当 l 越过 r 时返回 l 的值即可。
时间复杂度:O(n) 当数组只有很少的元素重复时,达到最坏复杂度 O(n);但如果数组重复的元素很多,此方法可以达到 O(logn)的效率。
空间复杂度:O(1)
实现:
1 | class Solution { |