首页 > 试题广场 >

有序数组删除重复数字

[编程题]有序数组删除重复数字

热度指数：14814 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个已排序的数组，使用就地算法将重复的数字移除，使数组中的每个元素只出现一次，返回新数组的长度。

不能为数组分配额外的空间，你必须使用常数级空间复杂度的就地算法。

例如，
给定输入数组 A=[1,1,2]，

你给出的函数应该返回length=2，A数组现在是[1,2]。

算法知识视频讲解

何恺明的小迷妹

// STL 骚操作
class Solution {
public:
    int removeDuplicates(int A[], int n) {
        if(n==0) return 0;
        if(n==1) return n;
        
        auto dup = unique(A,A+n);
        return dup-A;
    }
};

发表于 2018-08-19 09:38:14 回复(0)

更多回答

页川先生

count记录不重复元素的个数
    int removeDuplicates(int A[], int n) {
        if(A==NULL||n<=1)
            return n;
        int count=1;
        for(int i=1;i<n;i++){
            if(A[i]!=A[i-1]){
                A[count++]=A[i];
            }
        }
        return count;
    }

发表于 2017-11-05 19:37:37 回复(1)

C/C++

nbgao

class Solution {
public:
    int removeDuplicates(int A[], int n) {
    	if(n <= 0)
    		return 0;
    		
		int k=0;
    	for(int i=1;i<n;i++)
    	{
    		if(A[k] != A[i])
    			A[++k] = A[i];
		}
		return k+1;
    }
};

发表于 2017-07-29 18:06:31 回复(0)

C/C++

QT菜鸡弟弟

class Solution {
public:
    int removeDuplicates(int A[], int n) {
        if(n<=0)
            return 0;
        set<int> s;
        vector<int> vec;
        for(int i=0;i<n;i++)
        {
            if(s.insert(A[i]).second)
                vec.push_back(A[i]);
        }
        int size = s.size();
        for(int i=0;i<size;i++)
        {
            A[i]=vec[i];
        }
        return size;
    } 
};

发表于 2019-09-19 15:05:36 回复(0)

shijiacheng

/**
 * 26.Remove Duplicates from Sorted Array
 * 删除排序数组中的重复项
 * 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
 * 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 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。
 * 你不需要考虑数组中超出新长度后面的元素。
 */
public class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0){
            return 0;
        }

        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[index] != nums[i]){
                nums[++index] = nums[i];
            }
        }
        return index + 1;
    }


    public static void main(String[] args){
        int[] nums = {0,0,1,1,1,2,2,3,3,4};
        Solution s = new Solution();
        int length = s.removeDuplicates(nums);
        System.out.println(length);
    }
}

发表于 2018-09-05 21:31:41 回复(1)

C++

勇敢牛牛，不怕困难！

class Solution {
public:
  int removeDuplicates(int A[], int n) {
    // boundary case
    if (!n) return 0;
    
    int k = 0;
    for (int i = 1; i < n; ++i)
      if (A[i] != A[i - 1]) A[++k] = A[i];
      
    return k + 1;
  }
};

发表于 2021-09-28 11:29:25 回复(0)

C/C++

努力的牛牛

    //方法一：
    int removeDuplicates(int A[], int n) {
        int step = 0;
        for (int i = 0; i < n;++i){
            if (i== n-1 || A[i]!= A[i+1]){
                swap(A[i], A[i-step]);
            }
            else{
                step++;
            }
        }
        return n-step;
    }
    //方法二：
    int removeDuplicates(int A[], int n) {
        int index=0;
        for (int i = 0; i <= n-1;++i){
            if (i!= n-1 && A[i]==A[i+1])
                continue;
            A[index++]=A[i];
        }
        return index;
    }

发表于 2019-12-10 21:48:33 回复(0)

zbbsyx

class Solution {
public:
    int removeDuplicates(int A[], int n) {
        int len = 0,i = 0;
        while( i < n){
            if(!i || A[i] != A[i-1]) A[len++] = A[i]; 
            i ++;
        }
        return len;
    }
};

发表于 2019-05-28 16:16:44 回复(0)

mkckr

class Solution {
public:
    int removeDuplicates(int A[], int n)
    {
        int x = 0;
        for (int i = 0; i < n; i++) {
            if (i == 0 || A[i] != A[x - 1]) {
                A[x++] = A[i];
            }
        }
        return x;
    }
};

发表于 2019-05-11 11:16:22 回复(0)

Java

圣诞节的安徒生

public class Solution {
public int removeDuplicates(int[] A) {
int len = A.length;
if(len==0){
return 0;
}
int new_len = 0;
int i,j;
int flag = A[0];
for(i=1;i<len;i++){
int step =0;
j = i;
while(j<len&&A[j]==flag){
step++;
j++;
}
if(j==len){
break;
}
flag = A[j];
for(j=i;j<len&&j<i+step;j++){
A[j] = A[i+step];
}
}
flag = A[0];
new_len = 1;
for(i=1;i<len;i++){
if(A[i]!=flag){
new_len++;
flag = A[i];
}else{
break;
}
}
return new_len;
}

}

采用了一种十分复杂的方法，每次遇到重复的，则后面的数字向前进，过程十分曲折，结题思路不推荐！！！

下面算是正确的解题思路：

编辑于 2018-09-24 16:07:41 回复(0)

我菜得抠脚

  public int removeDuplicates(int[] A) {
        if(A.length<1) return 0;
        if(A.length==1) return 1;
        //记录不重复元素个数，仔细观察其实两个可以合并，这里为了方便理解
        int count=1;
        //记录不重复开始的索引
        int index=1;
        for(int i=0;i<A.length-1;i++) {
            if(A[i]!=A[i+1]) {
                count++;
                A[index++]=A[i+1];
            }
        }
        return count;
    }

发表于 2018-05-30 23:29:32 回复(0)

此广告位出租

public class Solution {
    public int removeDuplicates(int[] A) {
        int i=0,j=0;
        for (; i<A.length; i++){
            if (A[i] == A[j]){
                continue;
            }
            j++;
            A[j] = A[i];
        }
        return j+1;
    }
}

编辑于 2018-05-22 15:58:40 回复(0)

C/C++

class Solution {
public:
    int removeDuplicates(int A[], int n)
    {
        if(n<=0)
            return 0;
        int count=1;
        for(int i=1;i!=n;++i)
        {
            if(A[i]==A[i-1])
                continue;
            else
                A[count++]=A[i];
        }
        return count;
    }
};

发表于 2017-08-11 14:34:11 回复(0)

好好学习->天天向上

            class Solution {
public:
    int removeDuplicates(int A[], int n) {
        if (n == 0) return 0;
        
        int slow(1), fast(1);
        while(fast < n){
            while(fast < n && A[fast] == A[fast-1])	fast++;
            if (fast < n)
            	A[slow++] = A[fast++];
        }
        
        return slow;
    }
};

使用快慢两个“指针”，慢指针指向新数组末尾的下一个位置，快指针遍历原数组，当快指针检测到某个数和前一个数不相同的时候，把这个数赋值给慢指针，然后快慢指针均向右移动一格，直到快指针遍历完数组，返回慢指针的值即为长度。

发表于 2016-08-14 17:10:43 回复(1)

刘培强中校请回到休眠舱

class Solution {
public:
    int removeDuplicates(int A[], int n) { 
        if (n == 0) return 0; //空数组跳过
        int i = 0, j = 0; //维护两个指针
        while (++j < n) { //往后逐一遍历
            if (A[i] != A[j]) { //如若相等则跳过
                A[++i] = A[j]; //不相等则更新在i指针的后面             }
        }
        return ++i;
    }
};

发表于 2018-07-28 23:51:12 回复(0)

C/C++

G-Crisis

class Solution {
public:
    int removeDuplicates(int A[], int n) {
        if(n<=0)
            return 0;
        int a=A[0];
        int k= 1;
      //   printf("%d %d %d",n,A[1],A[2]);
        for(int i=1;i<n;i++)
        {
           /// printf("%d ",A[0]);
            if(a!=A[i])
            {
                a=A[i];
                A[k] = A[i];
                k++;
            }
        }
        return k;
    }
};

为什么提示错误？

编辑于 2021-12-28 17:47:08 回复(0)

C++

海饼干666

class Solution {
public:
    int removeDuplicates(int A[], int n) {
        if(n <= 1) return n;
        int cnt = 1;
        for(int i = 1; i < n; i++)
        {
            if(A[i] != A[i-1]) 
            {
                A[cnt] = A[i];
                cnt++;
            }
        }
        return cnt;
    }
};

发表于 2021-09-01 09:38:37 回复(0)

C/C++

ButterFlyEffect

本质上是双指针，pos是当前无重复数组的end，check是在检查的数组位置。每一轮执行一次check到pos+1的赋值。

class Solution {
public:
    int removeDuplicates(int A[], int n) {
        if(n <= 1) return n;
        int pos = 0, check = 1;
        while(check < n) {
            if(A[check] == A[pos]) {
                while(check < n && A[check] == A[pos]) check++;
            }
            if(check < n) {
                A[++pos] = A[check++];
            }
        }
        return pos+1;
    }
};

发表于 2020-11-24 10:33:07 回复(0)

ponmmains

public class Solution {
public int removeDuplicates(int[] A) {
int cnt = 0;
for (int i = 1; i < A.length; i++)
if (A[i - 1] == A[i]) cnt++;
else A[i - cnt] = A[i];

return A.length - cnt;
}
}

发表于 2020-10-08 16:18:14 回复(0)

科学xx

public int removeDuplicates(int[] A) {
int len = 0;
for (int i = 1; i < A.length-len; i++) {
if (A[i-1] == A[i]){//与下一个是否相等,删除当前元素
for (int j = i; j < A.length-1-len; j++) {
A[j] = A[j+1];
}
len++;
//移动后有可能相等，需要继续当前位置比较
i--;
}
}
return A.length-len;

}

//记录当前不重复的数

int len = 1;
for (int i = 1; i < A.length; i++) {
if (A[i-1] != A[i]){
A[len++] = A[i];
}
}
return len;

编辑于 2020-08-16 15:48:53 回复(0)

tofine

public class Solution {
public int removeDuplicates(int[] A) {
int count=1;
for(int i=0;i<A.length-1;i++){
if(A[i]!=A[i+1])
A[count++]=A[i+1];
}
return count;
}
}

发表于 2020-07-17 17:24:54 回复(0)