1. Dotnet9首页
  2. .NET
  3. .NET相关

删除排序数组中的重复项

给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

不要使用额外的数组空间,你必须在原地修改输入数组并在使用 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 是以“引用”方式传递的。也就是说,不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
  print(nums[i]);
}

来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

这道题目难度是简单。题目要求我们将排序数组中的重复项删除掉,并且不需要考虑数组中超出新长度后面的元素,而且不能使用额外的数组空间。这些要求给我们了思路,需要在原有的数组中进行修改,将所有的重复的元素进行移除。那么我们就考虑使用双指针法,一个指针用来遍历整个数组,一个指针用来记录修改后的数组尾部位置。还有题目中的说明,要求我们返回数值为整数,应为输入的数组是以“引用”方式传递的,我们需要返回的是新数组内容的长度,那么我们的代码可以构建如下:

public int RemoveDuplicates(int[] nums)
{
   if (nums == null)//空数组返回0
  {
       return 0;
  }
   if (nums.Length <= 1)//数组长度小于等于1 返回数组长度(0和1长度的数组都不会有重复项目)
  {
       return nums.Length;
  }
   int j = 0;
   for (int i = 1; i < nums.Length; i++)//指针i用于遍历数组
  {
       if (nums[i] != nums[j])
      {
           j++;//指针j,用于记录位置
           nums[j] = nums[i];
      }
  }
   return j + 1;//数组的长度为j+1
}

放入LeetCode跑一下

执行用时 :284 ms, 在所有 C# 提交中击败了98.60%的用户

内存消耗 :32.4 MB, 在所有 C# 提交中击败了65.79%的用户

性能不错,这个算法的时间复杂度为O(n),空间复杂度因为只使用两个指针量为常数个数变量,所以为O(1),符合题目要求,那么这道题目就讲到这里吧。

原文出处:微信公众号【IP的dotNet】,作者【IP的dotNet】

原文链接:https://mp.weixin.qq.com/s/GyzgIkL0RKLQl1QttYeF-Q

本文观点不代表Dotnet9立场,转载请联系原作者。

发表评论

登录后才能评论