删除有序数组中的重复项
给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。
不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。输入:nums = [1, 1, 2]
输出:2, nums = [1, 2]
快慢指针分别在索引为0和1的位置,慢指针时钟指向不重复序列的最后一位,快指针则否则遍历
遇到与慢指针相同时就继续++,不同时则慢指针后移,将下一个不重复的数字复制过来
class Solution { public: int removeDuplicates(vector<int>& nums) { if (nums.size() == 0) return 0; int low = 0, fast = 1; while (fast < nums.size()) { if (nums[low] != nums[fast]) {//不相等时,快指针复制到慢指针的下一位;相等时只有快指针+1 low++; nums[low] = nums[fast]; } fast++; } return low + 1; } }; 时间复杂度:O(n),假设数组的长度是 n,那么 i 和 j 分别最多遍历 n步。 空间复杂度:O(1)
升级:
给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 最多出现k次 ,返回删除后数组的新长度。
//------------------------------------way1 class Solution { public: //定义通用函数,使每个元素最多出现k次 int remove(vector<int>& nums, int k) { if (nums.size() <= k) return nums.size(); int low = k, fast = k;//low始终指向已排好的新数组的下一位 while (fast < nums.size()) { if (nums[low - k] != nums[fast]) { // k=2时候 3(low-2) 3 xlow 3(fast) 视为重复,此时low - k=fast nums[low] = nums[fast]; low++; } fast++; } return low; }
//------------------------------------way2 public: //定义通用函数,使每个元素最多出现k次 int remove(vector<int>& nums, int k) { if (nums.size() <= k) return nums.size(); int low = k - 1, fast = k;//low始终指向已排好的新数组的最后一位 while (fast < nums.size()) { if (nums[low - k + 1] != nums[fast]) { // k=2时候 3(low-1) 3(low) 3(fast) 视为重复,此时 low - k + 1=fast low++; nums[low] = nums[fast]; } fast++; } return low + 1; }