首页 > 试题广场 >

删除有序数组中重复的元素 ii

[编程题]删除有序数组中重复的元素 ii

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

给定一个有序数组，删除其中部分元素，使得剩下的每个数最多出现2次。要求删除的数的数量尽可能少。

例如：

给出有序数组 A =[1,1,1,2,2,3],

你给出的函数应该返回length =5, A 变为[1,1,2,2,3].

算法知识视频讲解

C/C++

搁浅的鱼儿

方法一：很灵活的方法，扩展性较强，如果将occur<2 改为 occur<3 ，就变成了允许重复最多三次

class Solution {
public:
    int removeDuplicates(int A[], int n) {
        if(n<=2) return n;
        int index=2;//允许重复两次，可以修改为三次
        for(int i=2;i<n;i++)
        {
            if(A[i]!=A[index-2])//允许重复两次，可以修改为三次
                A[index++]=A[i];
        }
        
        return index;
    }
};

方法二：简洁版本

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

编辑于 2016-07-13 21:49:17 回复(9)

后劲好大

常规思路吧。。
public class Solution {
    public int removeDuplicates(int[] A) {
        if(A == null || A.length <= 0)
        	return 0;
        int count = 1;
        int inx = 0;
        for(int i = 1; i < A.length; i++){
        	if(A[inx] != A[i]){
        		A[++inx] = A[i];
        		count = 1;
        	}
            // 相等的时候多判断一次即可
        	else{
        		count++;
        		if(count < 3){
        			A[++inx] = A[i];
        		}       		
        	}
        }
        return inx + 1;
    }
}

发表于 2017-05-04 16:21:03 回复(0)

C/C++

nbgao

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

发表于 2017-08-10 01:45:10 回复(0)

我不是匠人

双指针经典题

class Solution {
public:
    int removeDuplicates(int A[], int n) {
        int k = 0;
        for(int i = 0; i < n;){
            int j = i;
            while(j < n && A[i] == A[j]) j++;
            if( j - i >= 2){
                 A[k++] = A[i];
                 A[k++] = A[i];
            }else{
                A[k++] = A[i];
            }
            i = j;
        }
        return k;
    }
};

发表于 2019-12-14 12:31:35 回复(0)

C/C++

努力的牛牛

    /*
    * 目的：数组中元素最多容许重复两次
    * 方法1：使用计数排序的思想，时间复杂度和空间复杂度都是O(n)
    * 方法2：通过控制，插入重复数字的第一个和最后一个，
        *       时间复杂度为O(n),空间复杂度为O(1)
    * 方法3：扩展性比较强的方法，参考大佬
    */
    //方法一：
    int removeDuplicates(int A[], int n) {
        if (A==nullptr|| n<=2)
            return n;
        map<int, int>st;
        for (int i = 0; i< n;++i){
            st[A[i]]++;
        }
        int len = 0;
        for (auto it = st.begin();it!=st.end();++it){
            for (int j = 0; j < min(2, it->second);++j){
                A[len++]=it->first;
            }
        }
        return len;
    }
    //方法二：
    int removeDuplicates(int A[], int n) {
        if (A==nullptr|| n<=2)
            return n;
        int length=0;
        int count = 1;
        for (int i = 0; i < n; ++i){
            if (i == n-1 || A[i] !=A[i+1]){
                A[length++] = A[i];
                count = 1;
            }
            else{
                count++;
                if (count<3){
                    A[length++]= A[i];
                }
            }
        }
        return length;
    }
    //方法三：扩展性很强，如果容许重复三次，只需将间隔改为3即可
    int removeDuplicates(int A[], int n) {
        if (A==nullptr|| n<=2)
            return n;
        int index = 2;
        for (int i = 2;i < n;++i){
            if (A[i]!=A[index-2])
                A[index++]=A[i];
        }
        return index;
    }

编辑于 2019-12-09 10:28:48 回复(0)

lollipop😈😈

public class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        int k = 1;// 保证nums中[0, k)中无出现两次以上元素
        int count = 1;// 记录当前元素出现次数
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[k - 1]) {// 与上一次重复
                if (count == 1) {// 当前为出现第二次
                    nums[k++] = nums[i];
                    count++;
                }
            } else {// 当前为新元素
                count = 1;
                nums[k++] = nums[i];
            }
        }
        return k;
    }
}

发表于 2019-01-27 12:34:31 回复(0)

C/C++

J.Fan

//思路很简单，就是用p和q双标志来遍历，p表示符合题目的下标，q表示原数组下标，每次先给p下标
//赋值q下标值，然后判断q后面是否有重复值，有的话，就让q指向最后一个重复着，给p+1再赋一次值
class Solution {
public:
    int removeDuplicates(int A[], int n) {
        if(n<=2)
            return n;
        int p,q;
        p = 0;q = 0;
        int flag;
        while(q<n)
        {
            A[p++] = A[q];
            flag = 0;
            while(q+1<n && A[q]==A[q+1])
            {
                flag = 1;
                q++;
            }
            if(flag)
                A[p++] = A[q];
            q++;
        }
        return p;
    }
};

发表于 2019-01-09 15:06:17 回复(0)

C/C++

F-L

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

发表于 2018-03-29 21:11:43 回复(0)

丶沉梦昂志

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

编辑于 2017-11-25 22:11:16 回复(0)

sky_

//Index表示现在要放置新建数组index位置的数值，i表示检测到了原数组i位置，那么i能放在
//index位置的唯一条件就是a[i]!=a[index-2].
class Solution {
public:
    int removeDuplicates(int A[], int n) {
        if(n<=2) return n;
        int index=2;
        for(int i=2;i<n;i++){
            if(A[i]!=A[index-2])
               A[index++]=A[i]; 
        }
        return index;
    }
};

发表于 2017-07-31 09:13:05 回复(0)

Java

詆調壹點

import java.util.*;
public class Solution {
    public static int removeDuplicates(int[] A) {
		if(A.length == 0) return 0;
		List<Integer> list = new ArrayList<>();
		list.add(A[0]);
		int count = 1;
		for (int i = 1; i < A.length; i ++ ) {
			if(A[i] == A[i - 1]) count ++ ;
			else count = 1;
			if(count == 1 || count == 2) list.add(A[i]);
		}
		for (int i = 0; i < list.size(); i ++ ) {
			A[i] = list.get(i);
		}
		return list.size();
	}
}

发表于 2016-11-06 17:21:36 回复(0)

已注销

  if (n <= 2)return n;

		int index = 1;
		for (int i = 1; i < n-1; i++)
		{
			if (A[index- 1] != A[i+1])
			{
				index++;
				A[index] = A[i+1];
			}
		}
		return index + 1;

发表于 2016-03-19 00:00:45 回复(0)

徐文达

int removeDuplicates(int* A, int ALen)
{
    int i = 0;
    int j = 0;
    int count = 0;

    for (i = 0; i < ALen - count - 2; i++)
    {
        //判断是否有重复3个的元素
        if (A[i] == A[i + 1] && A[i + 1] == A[i + 2])
        {
            //记录已经删除的个数
            count++;
            //删除第3个元素
            for (j = i + 2; j < ALen - count; j++)
            {
                A[j] = A[j + 1];
            }
            //返回上一元素，检查是否仍然重复3个
            i--;
        }
    }
    return ALen - count;
}

编辑于 2024-03-22 21:38:51 回复(0)

C/C++

华科不平凡

一个通用的思路：用index记录新数组的下标，遍历旧数组，如果当前元素与A[index-2]的元素不相同，则表示这个数应该放入新数组。（其中2可以变为1,3,4...）代码如下：

//
// Created by jt on 2020/9/24.
//
class Solution {
public:
    int removeDuplicates(int A[], int n) {
        if (n <= 2) return n;
        int idx = 2;
        for (int i = 2; i < n; ++i) {
            if (A[idx-2] != A[i]) {
                A[idx++] = A[i];
            }
        }
        return idx;
    }
};

发表于 2020-09-24 17:45:22 回复(0)

Python

黄沙遮天

#
# 
# @param A int整型一维数组 
# @return int
#
class Solution:
    def removeDuplicates(self , A ):
        # write code here
        n=len(A)
        if n<2:
            return n
        s=2
        for i in range(2,n):
            if A[i]!=A[s-2]:
                A[s]=A[i]
                s+=1
        return s

其中s表示实际列表中元素重复次数不超过两个的时候的元素的个数

发表于 2020-08-24 11:08:21 回复(0)

科学xx

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

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

要暴富的小刺猬很高大

```c++

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

```

发表于 2020-07-12 15:04:17 回复(0)

merlinssea

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

发表于 2020-04-18 17:35:15 回复(0)

野猪佩琪🐗

Java常规思路

public class Solution {
    public int removeDuplicates(int[] A) {
        if(A==null)
            return 0;
        int k = 0;
        boolean two = false;    //已经出现了2个相同
        for(int i=1;i<A.length;i++){
            if(A[i]==A[k]){
                if(!two){        
                    two = true;
                    A[++k] = A[i];
                }
            }else{
                A[++k] = A[i];
                two = false;
            } 
        }
        return k+1;
    }
}

发表于 2020-02-17 22:24:25 回复(0)

ponmmains

public class Solution {
public int removeDuplicates(int[] A) {
if (A == null || A.length == 0)
return 0;

int len = 1, cnt = 1, pVal = A[0];
int[] B = new int[A.length];
B[0] = A[0];
for (int i = 1; i < A.length; i++) {
if (A[i] == pVal) {
if (cnt == 1)
B[len++] = A[i];
cnt++;
}else {
B[len++] = A[i];
pVal = A[i];
cnt = 1;
}
}

for (int i = 0; i < len; i++)
A[i] = B[i];
return len;
}
}

发表于 2020-01-11 14:43:52 回复(0)