首页 > 代码库 > [Leetcode] Remove duplicates from sorted array 从已排序的数组中删除重复元素

[Leetcode] Remove duplicates from sorted array 从已排序的数组中删除重复元素

2024-10-15 02:12:39   215人阅读

Given a sorted array, 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 in place with constant memory.

For example,
Given input array A =[1,1,2],

Your function should return length =2, and A is now[1,2].

题意：除去重复的元素，若有重复只保留一个，返回长度。

思路：遍历数组，用不同的，覆盖相同的。过程：保存第一个元素的下标lo。遇到相等不管，继续遍历，遇到不等的，则将该值赋给lo的下一个，反复这样。代码如下：

 1 class Solution
 2 {   
 3 public:
 4     int removeDuplicates(int A[],int n)
 5     {
 6         if(n<=0)    return 0;
 7         int lo=0;
 8         for(int i=1;i<=n-1;++i)
 9         {
10             if(A[lo] !=A[i])
11                 A[++lo]=A[i];
12         }
13         return lo+1;
14     }
15 };

思路相同，另一种写法：

 1 class Solution {
 2 public:
 3     int removeDuplicates(int A[], int n) 
 4     {
 5         if(n<2) return n;
 6         int count=1;
 7         int flag=0;
 8         for(int i=0;i<n;++i)
 9         {
10             if(A[flag] !=A[i])
11             {
12                 A[++flag]=A[i];
13                 count++;
14             }
15         }    
16         return count;
17     }
18 };

 

[Leetcode] Remove duplicates from sorted array 从已排序的数组中删除重复元素


联系
我们