Python删除有序数组的重复项（附其他语言实现）
做一个柔情的程序猿
共 2019字，需浏览 5分钟
·
2021-12-12 08:14
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1：输入：nums = [1,1,2] 输出：2, nums = [1,2]
示例 2：输入：nums = [0,0,1,1,1,2,2,3,3,4] 输出：5, nums = [0,1,2,3,4]
解题思路
注意为有序数组，把数组nums分成两个数组，一个新的无重复元素的数组nums[0:i]，一个数组nums[j, len(nums)]
采用双指针，一个指针j指向数组nums[j, len(nums)]，当nums[j] == nums[i]时，指针向右移;
一个指针i指向新的无重复元素的数组nums[0:i]，当nums[j] != nums[i]时，新数组增加长度，i=i+1，nums[i] = nums[j]
得到新的数组nums[0:i]，返回新数组的长度i+1
set 就是为了实现去重的。但是要求进行原地操作，并且时间复杂度是 O(1)，因此就不能开辟另外的空间。则必须有一个指针指向当前需要把结果放在哪个位置，还要一个指针指向当前应该放到哪个元素。
代码实现
python/
class Solution:def removeDuplicates(self, nums):i = 0for j in range(1, len(nums)):if nums[j] != nums[i]:i += 1nums[i] = nums[j]return i + 1
C/
int removeDuplicates(int* nums, int numsSize){if(numsSize == 0){return 0;}int slow = 0, fast = 1;while(fast < numsSize){if(nums[fast] != nums[slow]){slow = slow + 1;nums[slow] = nums[fast];}fast = fast + 1;}return slow + 1;}
C++/
class Solution {public:int removeDuplicates(vector& nums) { const int N = nums.size();if (N == 0) return 0;int left = 0;for (int right = 1; right < N; ++right) {if (nums[left] != nums[right]) {nums[++left] = nums[right];}}return left + 1;}};
java/
class Solution {public int removeDuplicates(int[] nums) {int i = 0;for(int j = 0; j < nums.length; j++){if(nums[j] != nums[i]){nums[++i] = nums[j];}}return i + 1;}}
你需要的也许就在这里
只需要回头望望
我在这里等你哟
评论